Submission #1110976

#TimeUsernameProblemLanguageResultExecution timeMemory
1110976jerzykCatfish Farm (IOI22_fish)C++17
0 / 100
1087 ms201412 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, 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) { for(int i = 1; i < (int)dpv[l].size(); ++i) { for(int j = 0; j < (int)dpv[l - 2].size(); ++j) { if(dpv[l - 2][j] <= dpv[l][i]) dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j] - sr[l - 2][j] + sl[l][i]); else dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j]); } dp[l][1][i] = dp[l][0][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(0); 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...