Submission #652463

#TimeUsernameProblemLanguageResultExecution timeMemory
652463blueCatfish Farm (IOI22_fish)C++17
100 / 100
316 ms68660 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using pii = pair<int, int>; using vpii = vector<pii>; using vvpii = vector<vpii>; using vi = vector<int>; using vvi = vector<vi>; using pll = pair<ll, ll>; using vpll = vector<pll>; #define sz(x) int(x.size()) void selfmax(ll& a, ll b) { a = max(a, b); } const int maxN = 100'000; vpll fish[1 + maxN]; vll fishpref[1 + maxN]; vll tot(1 + maxN, 0); ll max_weights(int N, int M, vi X, vi Y, vi W) { vvll sm(2, vll(N, 0)); for(int j = 0; j < M; j++) if(X[j] < 2) sm[X[j]][Y[j]] += W[j]; if(N == 2) { return max(sm[0][0] + sm[0][1], sm[1][0] + sm[1][1]); } int xmx = 0; for(int j = 0; j < M; j++) { X[j]++; xmx = max(xmx, X[j] + 2); Y[j]++; } xmx = min(xmx, N); // cerr << "xmx = " << xmx << '\n'; vpll fish[1+N]; ll* fishpref[1+N]; vpii fishbyY[1+N]; for(int j = 0; j < M; j++) { // fish[X[j]].push_back({Y[j], W[j]}); fishbyY[Y[j]].push_back({X[j], W[j]}); tot[X[j]] += W[j]; } for(int y = 0; y <= N; y++) for(pii z : fishbyY[y]) fish[z.first].push_back({y, z.second}); for(int r = 1; r <= xmx; r++) { fish[r].push_back({N+1, 0}); // sort(fish[r].begin(), fish[r].end()); if(fish[r][0].first != 1) { fish[r].insert(fish[r].begin(), {1, 0}); } fishpref[r] = new ll[sz(fish[r])]; for(int i = 0; i < sz(fish[r]); i++) { fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second; } } fish[0] = vpll{{0, 0}}; fishpref[0] = new ll[1]; fishpref[0][0] = 0; // vvll inc(1+N), dec(1+N); ll* inc[1+N]; ll* dec[1+N]; ll* incpref[1+N]; ll* decpref[1+N]; //pref inc dec mx inc[0] = new ll[1]; inc[0][0] = 0; dec[0] = new ll[1]; dec[0][0] = 0; ll res = 0; // cerr << "done\n"; for(int r = 1; r <= xmx; r++) { incpref[r-1] = new ll[sz(fish[r-1])]; decpref[r-1] = new ll[sz(fish[r-1])]; incpref[r-1][0] = decpref[r-1][0] = 0; for(int i = 1; i < sz(fish[r-1]); i++) { incpref[r-1][i] = max(incpref[r-1][i-1], inc[r-1][i]); decpref[r-1][i] = max(decpref[r-1][i-1], dec[r-1][i]); } // inc[r] = dec[r] = vll(sz(fish[r]), 0); inc[r] = new ll[sz(fish[r])]; dec[r] = new ll[sz(fish[r])]; for(int i = 0; i < sz(fish[r]); i++) inc[r][i] = dec[r][i] = 0; vll Csuff; if(r >= 2) { Csuff = vll(sz(fish[r-2])); int pi = sz(fish[r-1])-1; ll pwt = tot[r-1]; for(int j = sz(fish[r-2])-1; j >= 0; j--) { while(pi >= 0 && fish[r-1][pi].first > fish[r-2][j].first - 1) { pwt -= fish[r-1][pi].second; pi--; } // Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1); Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + pwt; if(j+1 < sz(fish[r-2])) selfmax(Csuff[j], Csuff[j+1]); } } ll Dmx = 0; ll Did = -1; int ppi = -1; int qi = -1; ll qwt = 0; for(int i = 0; i < sz(fish[r]); i++) { ll basic = 0; ll Bcatch = 0; // int Bk = -1; ll oldqwt = qwt; while(qi+1 < sz(fish[r-1]) && fish[r-1][qi+1].first <= fish[r][i].first - 1) { qi++; qwt += fish[r-1][qi].second; } ll prevpwt = qwt; ll constD = -(tot[r-1] - prevpwt) + tot[r-1]; if(r >= 2) { //A selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + prevpwt); while(ppi+1 < sz(fish[r-2]) && fish[r-2][ppi+1].first <= fish[r][i].first) ppi++; int ploci = ppi; // while(Bk+1 < sz(fish[r-1]) && fish[r-1][Bk+1].first <= fish[r][i].first - 1) // { // Bk++; // Bcatch += fish[r-1][Bk].second; // } Bcatch = qwt; // assert(Bcatch == qwt); // assert(Bk == qi); selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci])); if(ploci+1 < sz(fish[r-2])) { // cerr << ploci << " : " << sz(fish[r-2]) << '\n'; selfmax(basic, Csuff[ploci+1]); } } selfmax(inc[r][i], basic); selfmax(dec[r][i], basic); //type D transition while(Did+1 < sz(fish[r-1]) && fish[r-1][Did+1].first <= fish[r][i].first) { Did++; Dmx = max(Dmx, inc[r-1][Did] - (Did >= 1 ? fishpref[r-1][Did-1] : 0)); } selfmax(inc[r][i], Dmx + constD); selfmax(dec[r][i], Dmx + constD); } int j = sz(fish[r-1]); ll bestval = -1'000'000'000'000'000'000LL; int ri = sz(fish[r]); ll rwt = 0; for(int i = sz(fish[r])-1; i >= 0; i--) { while(j-1 >= 0 && fish[r-1][j-1].first > fish[r][i].first) { j--; while(ri-1 >= 0 && fish[r][ri-1].first >= fish[r-1][j].first) { ri--; rwt += fish[r][ri].second; } bestval = max(bestval, dec[r-1][j] + tot[r] - rwt); } selfmax(dec[r][i], bestval - (i >= 1 ? fishpref[r][i-1] : 0)); } for(int i = 0; i < sz(fish[r]); i++) selfmax(res, max(inc[r][i], dec[r][i])); } return res; }

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, vi, vi, vi)':
fish.cpp:166:7: warning: unused variable 'oldqwt' [-Wunused-variable]
  166 |    ll oldqwt = qwt;
      |       ^~~~~~
#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...