IOI2009 "Salesman"
はじめてのあいおーあい。
ろくに確認もせずテストデータにとりあえず投げた結果玉砕し、その後しょーもないことで時間を潰した。
練習量が足りない。死にたい。
problem
IPSJの雑誌とテレビの両方で見かけたので解いてみようと思った。問題の名称がどう見てもTSP。
solution
IPSJのにはsegment treeって書いてあったけど所謂区間木じゃなくてBinaryIndexTreeの類だった。
ところでBinaryIndexTreeでググっても出てこないんだけど、この名称って間違ってるの?
source
#include <cstdio> #include <climits> #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <utility> #define MY_MIN (INT_MIN+500000000) using namespace std; int n,u,d,s; struct fair { int id, t, l, m, msum, ms0, ms1; fair() : msum(MY_MIN) {} bool operator<(const fair& o) const { if(t!=o.t) return t<o.t; return l<o.l; } }; struct bit { vector<int> prices; bit() : prices(1<<20, MY_MIN) {} void insert(int idx, int price) { for(int x = idx+(1<<19); x; x>>=1) { prices[x] = max(prices[x], price); } } int find_(int t) { if(t==0)return MY_MIN; int ret = find_(t>>1); if(t&1) { ret = max(ret, prices[t-1]); } return ret; } int find(int t) { return find_(t+(1<<19)); } }; vector<fair> fairs; int main(int argc, char **argv) { scanf("%d%d%d%d", &n, &u, &d, &s); fairs.resize(n+1); for(int i = 0; i < n; i++) { fairs[i].id = i; scanf("%d%d%d", &fairs[i].t, &fairs[i].l, &fairs[i].m); } fairs[n].id = -1; fairs[n].t = INT_MAX; fairs[n].l = s; fairs[n].m = 0; sort(fairs.begin(), fairs.end()); bit b_upside, b_downside; b_upside.insert(500010-s, 0-u*s); b_downside.insert(s, 0+d*s); int i = 0; while(i<fairs.size()) { int is = fairs.size(); for(int j = i; j < fairs.size(); j++) { if(fairs[i].t != fairs[j].t) { is = j; break; } fairs[j].msum = max(fairs[j].msum, b_upside.find(500010-fairs[j].l+1)+u*fairs[j].l); fairs[j].msum = max(fairs[j].msum, b_downside.find(fairs[j].l+1)-d*fairs[j].l); } for(int j = i; j < is; j++) { fairs[j].msum += fairs[j].m; } int current_max = MY_MIN; for(int j = i; j < is; j++) { fairs[j].ms0 = max(fairs[j].msum, current_max-d*fairs[j].l+fairs[j].m); current_max = fairs[j].ms0+d*fairs[j].l; } current_max = MY_MIN; for(int j = is-1; j >= i; j--) { fairs[j].ms1 = max(fairs[j].msum, current_max+u*fairs[j].l+fairs[j].m); current_max = fairs[j].ms1-u*fairs[j].l; } for(int j = i; j < is; j++) { fairs[j].msum = max(fairs[j].msum, fairs[j].ms0); fairs[j].msum = max(fairs[j].msum, fairs[j].ms1); b_upside.insert(500010-fairs[j].l, fairs[j].msum-u*fairs[j].l); b_downside.insert(fairs[j].l, fairs[j].msum+d*fairs[j].l); } i = is; } printf("%d\n", fairs[n].msum); return 0; }