제출 #723642

#제출 시각아이디문제언어결과실행 시간메모리
723642Luicosas메기 농장 (IOI22_fish)C++17
3 / 100
218 ms61132 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define sz(x) (int)(x.size()) #define itr(x) x.begin(), x.end() #define ref(x) (*(x)) #define prv(x) for(auto& pval : x) cout << pval << " "; cout << "\n"; #ifdef LOC #define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n"; #else #define debug(...) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> ostream& operator << (ostream& out, vector<T> v) { out << "{ "; for(auto& i : v) { out << i << " "; } out << "} "; return out; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { const int maxh = N + 5; vector<vector<array<int,2>>> xpoints(N); for(int i = 0; i < M; i++) { xpoints[X[i]].pb({Y[i], W[i]}); } for(auto& v : xpoints) { sort(itr(v)); } vector<vector<ll>> pfx(N); vector<vector<int>> dp_idxs(N); for(int x = 0; x < N; x++) { if(sz(xpoints[x]) == 0 || xpoints[x][0][0] > 1) { pfx[x].pb(0); dp_idxs[x].pb(0); } for(auto& p : xpoints[x]) { if(p[0] != 0 && (!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0] - 1)) { pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0)); dp_idxs[x].pb(p[0] - 1); } if(!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0]) { pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0) + p[1]); dp_idxs[x].pb(p[0]); } } pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0)); dp_idxs[x].pb(maxh); } debug(pfx); debug(dp_idxs); vector<vector<ll>> inc_dp(N), dec_dp(N); inc_dp[0].assign(sz(dp_idxs[0]), 0); dec_dp[0].assign(sz(dp_idxs[0]), 0); for(int x = 1; x < N; x++) { int psz = sz(dp_idxs[x - 1]), csz = sz(dp_idxs[x]); // calc inc_dp inc_dp[x].assign(sz(dp_idxs[x]), 0); ll gmx = 0; int gptr = psz - 1; for(int i = csz - 1; i >= 0; i--) { ll h = dp_idxs[x][i]; while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) { ll v = max(inc_dp[x - 1][gptr], dec_dp[x - 1][gptr]); gmx = max(gmx, v + pfx[x][i]); gptr--; } inc_dp[x][i] = max(inc_dp[x][i], gmx - pfx[x][i]); } dec_dp[x].assign(csz, 0); ll smx = 0; int sptr = 0; for(int i = 0; i < csz; i++) { ll h = dp_idxs[x][i]; while(sptr < psz && dp_idxs[x - 1][sptr] < h) { ll v = dec_dp[x - 1][sptr]; smx = max(smx, v - pfx[x - 1][sptr]); sptr++; } dec_dp[x][i] = max(dec_dp[x][i], smx + pfx[x - 1][sptr]); } if(x == 1) { continue; } int ppsz = sz(dp_idxs[x - 2]); int gpptr = ppsz - 1; gptr = psz - 1; ll gppmx = 0, gvmx = 0; for(int i = csz - 1; i >= 0; i--) { ll h = dp_idxs[x][i]; while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) { while(gpptr >= 0 && dp_idxs[x - 2][gpptr] >= dp_idxs[x - 1][gptr]) { gppmx = max(gppmx, dec_dp[x - 2][gpptr]); gppmx = max(gppmx, inc_dp[x - 2][gpptr]); gpptr--; } gvmx = max(gvmx, pfx[x - 1][gptr] + gppmx); gptr--; } dec_dp[x][i] = max(dec_dp[x][i], gvmx); } } debug(inc_dp); debug(dec_dp); ll ans = 0; for(auto& p : inc_dp[N - 1]) { ans = max(ans, p); } for(auto& p : dec_dp[N - 1]) { ans = max(ans, p); } 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...