제출 #626171

#제출 시각아이디문제언어결과실행 시간메모리
626171TheLostCookie메기 농장 (IOI22_fish)C++17
0 / 100
1096 ms82440 KiB
#include <bits/stdc++.h> #include "fish.h" using namespace std; typedef long long int lli; typedef vector<lli> vi; typedef pair<lli,lli> ii; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i) #define pb push_back #define fi first #define se second #define all(v) begin(v),end(v) const lli INF = 4e18; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { map<ii,lli> inc, dec; inc[{-1,-INF}] = dec[{-1,-INF}] = 0; inc[{-1,INF}] = dec[{-1,INF}] = 0; vector<pair<ii,lli>> ptw; FOR(i,0,M) ptw.pb({{X[i],Y[i]},W[i]}); FOR(i,0,N) ptw.pb({{i,INF},0}); sort(all(ptw)); vector<ii> pts; vector<lli> wts{0}; FOR(i,0,M+N) { pts.pb(ptw[i].fi); wts.pb(wts.back()+ptw[i].se); } //counts fish in [{x,y1},{x,y2}], inclusive of endpoints function<lli(lli,lli,lli)> countFish = [&] (lli x, lli y1, lli y2) { if(y1 > y2) return 0LL; else { int l = lower_bound(all(pts),ii{x,y1}) - begin(pts); int r = upper_bound(all(pts),ii{x,y2}) - begin(pts); return wts[r]-wts[l]; } }; FOR(i,0,N) { map<ii,lli> colInc[3]; map<ii,lli> colDec; int l = lower_bound(all(pts), ii{i,0}) - begin(pts); int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts); int p = lower_bound(all(pts), ii{i-2,0}) - begin(pts); FOR(j,l,r) { if(j>l) colInc[0][pts[j]]=max(colInc[0][pts[j]],colInc[0][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1)); while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<pts[j].se) { colInc[0][pts[j]]=max(colInc[0][pts[j]],dec[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1)); p++; } } p = lower_bound(all(pts), ii{i-2,0}) - begin(pts); while(p<int(pts.size())&&pts[p].fi==i-2) colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]),p++; FOR(j,l+1,r) colInc[1][pts[j]] = max(colInc[1][pts[j]],colInc[1][pts[j-1]]); p = lower_bound(all(pts), ii{i-1,0}) - begin(pts); FOR(j,l,r) { if(j>l) colInc[2][pts[j]]=max(colInc[2][pts[j]],colInc[2][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1)); while(p<int(pts.size())&&pts[p].fi==i-1&&pts[p].se<pts[j].se) { colInc[0][pts[j]]=max(colInc[0][pts[j]],inc[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1)); p++; } } p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts); ROF(j,l,r) { if(j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+countFish(i,pts[j].se,pts[j+1].se-1)); while(p>=0&&pts[p].fi==i-1&&pts[p].se>pts[j].se) { colDec[pts[j]]=max(colDec[pts[j]],dec[pts[p]]+countFish(i,pts[j].se,pts[p].se-1)); p--; } } FOR(j,l,r) { FOR(k,0,3) { inc[pts[j]] = max(inc[pts[j]],colInc[k][pts[j]]); } dec[pts[j]] = max(dec[pts[j]],colDec[pts[j]]); } assert(dec[ii({i,INF})] == 0); dec[ii{i,INF}] = inc[ii{i,INF}]; } lli ans = max(inc[{N-1,INF}],dec.lower_bound({N-1,0})->second); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...