誤読で時間を浪費した。
https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_f
問題
N個の果物をN日間に1個ずつ食べていく。
i番の果物は元のおいしさがA[i]であり、食べごろがT[i]日目なのでそこから離れた日に食べるとおいしさが1日あたりB[i]減少する。
果物を最適な順で食べる場合、N日間の最低のおいしさの最高値はいくつになるか。
解法
二分探索で解く。
おいしさを定めれば、各果物をそのおいしさ以上で食べられる日の区間が求まるので、区間スケジューリングの要領でN個の区間でN日をカバーできるか判定すればよい。
int N; ll T[202020]; ll S,A[202020],B[202020]; vector<int> ev[202020]; int ok(ll v) { int i; FOR(i,N) ev[i].clear(); FOR(i,N) { if(A[i]<v) return 0; ll d=(A[i]-v)/B[i]; ll L=max(T[i]-d,0LL); ll R=T[i]+d; ev[L].push_back(R); } multiset<int> T; FOR(i,N) { FORR(e,ev[i]) T.insert(e); while(T.size() && *T.begin()<i) return 0; if(T.empty()) return 0; T.erase(T.begin()); } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>T[i]>>A[i]>>B[i]; T[i]--; } ll ret=-1LL<<30; for(i=30;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i; cout<<ret<<endl; }
まとめ
最初おいしさの総和を最大化しようとしちゃった。
それでも500-600ptかな。