Submission #1110984

#TimeUsernameProblemLanguageResultExecution timeMemory
1110984jerzykCatfish Farm (IOI22_fish)C++17
47 / 100
1076 ms226196 KiB
#include <bits/stdc++.h> #include "fish.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1000 * 1000 + 7; vector<pair<int, ll>> cat[N]; vector<int> dpv[N]; vector<ll> dp[N][2], sl[N], as[N], sr[N]; void CntS(int n) { for(int l = 0; l <= n; ++l) { int j1 = 0, j2 = 0, j3 = 0; ll s1 = 0, s2 = 0, s3 = 0; //cerr << l << " " << dpv[l].size() << " " << as[l].size() << "\n"; for(int i = 1; i < (int)dpv[l].size(); ++i) { while(l > 0 && j1 < (int)cat[l - 1].size() - 1 && cat[l - 1][j1 + 1].st <= dpv[l][i]) { ++j1; s1 += cat[l - 1][j1].nd; } while(j2 < (int)cat[l].size() - 1 && cat[l][j2 + 1].st <= dpv[l][i]) { ++j2; s2 += cat[l][j2].nd; } while(j3 < (int)cat[l + 1].size() - 1 && cat[l + 1][j3 + 1].st <= dpv[l][i]) { ++j3; s3 += cat[l + 1][j3].nd; } //cerr << i << " "; sl[l][i] = s1; as[l][i] = s2; sr[l][i] = s3; } } } void Do1() { for(int i = 1; i < (int)dpv[1].size(); ++i) { dp[1][0][i] = sr[1][i]; //dp[1][2][i] = sr[1][i]; } } void CntDP(int n) { Do1(); for(int l = 2; l <= n; ++l) { ll ma = -I, mb = -I; for(int j = 0; j < (int)dpv[l - 2].size(); ++j) { ma = max(ma, dp[l - 2][0][j] - sr[l - 2][j]); mb = max(mb, dp[l - 2][0][j]); } ll m1 = 0; int j1 = -1; for(int i = 0; i < (int)dpv[l].size(); ++i) { dp[l][0][i] = max(ma + sl[l][i], mb); dp[l][1][i] = dp[l][0][i]; while(j1 < (int)dpv[l - 1].size() - 1 && dpv[j1 + 1] <= dpv[i]) { ++j1; m1 = max(m1, dp[l - 1][1][j1] - as[l - 1][j1]); } dp[l][1][i] = max(dp[l][1][i], m1 + sl[l][i]); for(int j = 0; j < (int)dpv[l - 1].size(); ++j) { //if(dpv[l - 1][j] <= dpv[l][i]) //dp[l][1][i] = max(dp[l][1][i], dp[l - 1][1][j] + sl[l][i] - as[l - 1][j]); if(dpv[l - 1][j] >= dpv[l][i]) dp[l][0][i] = max(dp[l][0][i], dp[l - 1][0][j] - as[l][i]); } dp[l][0][i] = max(dp[l][0][i], dp[l][1][i]) + sr[l][i]; //cerr << l << " " << i << " " << dp[l][0][i] << " " << dp[l][1][i] << "\n"; } } } long long max_weights(int _N, int _M, vector<int> X, vector<int> Y, vector<int> W) { int n = _N, m = _M; for(int i = 0; i < m; ++i) {X[i] += 1; Y[i] += 1;} for(int i = 0; i <= n + 1; ++i) { dpv[i].pb(0); cat[i].pb(make_pair(0, 0LL)); } for(int i = 0; i < m; ++i) { cat[X[i]].pb(make_pair(Y[i], W[i])); if(X[i] > 1) dpv[X[i] - 1].pb(Y[i]); if(X[i] < N) dpv[X[i] + 1].pb(Y[i]); } for(int l = 0; l <= n; ++l) { sort(cat[l].begin(), cat[l].end()); sort(dpv[l].begin(), dpv[l].end()); vector<int> nw; for(int i = 0; i < (int)dpv[l].size(); ++i) if(i == 0 || dpv[l][i] != dpv[l][i - 1]) nw.pb(dpv[l][i]); dpv[l] = nw; for(int i = 0; i < (int)dpv[l].size(); ++i) dp[l][0].pb(0LL); dp[l][1] = dp[l][0]; sl[l] = dp[l][0]; as[l] = dp[l][0]; sr[l] = dp[l][0]; } CntS(n); CntDP(n); //cerr << "XD\n"; ll ans = 0LL; for(int i = 1; i <= n; ++i) for(int j = 0; j < (int)dpv[i].size(); ++j) ans = max(ans, dp[i][0][j]); 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...