Submission #1067604

#TimeUsernameProblemLanguageResultExecution timeMemory
1067604mariaclaraCatfish Farm (IOI22_fish)C++17
3 / 100
96 ms35672 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef tuple<int,int,int> trio; #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb push_back #define mk make_pair #define fr first #define sc second ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { vector<ll> ans_col(N); vector<vector<pii>> val(N); vector<vector<ll>> dp[2]; dp[0].resize(N); // x-1 < x dp[1].resize(N); // x-1 > x for(int i = 0; i < M; i++) val[X[i]].pb({Y[i], W[i]}); dp[0][0].resize(sz(val[0])+1, 0); dp[1][0].resize(sz(val[0])+1, 0); for(int x = 1; x < N; x++) { sort(all(val[x])); reverse(all(val[x])); dp[0][x].resize(sz(val[x])+1); dp[1][x].resize(sz(val[x])+1); // > for(int i = 0, j = 0; i < sz(val[x]); i++) { auto [y,w] = val[x][i]; if(i != 0) dp[1][x][i+1] = dp[1][x][i] + w; while(j < sz(val[x-1]) and val[x-1][j].fr > y) j++; dp[1][x][i+1] = max(dp[1][x][i+1], dp[1][x-1][j] + w); // LEMBRAR DE dp[1][x][j] max= dp[1][x][j-1] //cout << "x = " << x << ", i = " << i << ", y = " << y << ", w = " << w << ", dp = " << dp[1][x][i+1] << "\n"; } // < ll w = 0, aux = 0; for(int i = sz(val[x]) - 1, j = sz(val[x-1]) - 1, y; i >= -1; i--) { if(i >= 0) y = val[x][i].fr; else y = N; dp[0][x][i+1] = max(dp[0][x][i+1], w); while(j >= 0 and val[x-1][j].fr < y) { w = max(w, dp[0][x-1][j+1]); w += val[x-1][j].sc; aux += val[x-1][j].sc; dp[0][x][i+1] = max(dp[0][x][i+1], w); j--; } if(x >= 2) dp[0][x][i+1] = max(dp[0][x][i+1], ans_col[x-2] + aux); //cout << "x = " << x << ", i = " << i << ", y = " << y << ", w = " << w << ", dp = " << dp[0][x][i+1] << "\n"; } dp[1][x][0] = max(dp[1][x][0], dp[0][x][0]); for(int i = 1; i <= sz(val[x]); i++) dp[1][x][i] = max({dp[1][x][i], dp[1][x][i-1], dp[0][x][i]}); ans_col[x] = dp[1][x][sz(val[x])]; } return ans_col[N-1]; }
#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...