Submission #1186833

#TimeUsernameProblemLanguageResultExecution timeMemory
1186833ByeWorldCatfish Farm (IOI22_fish)C++20
14 / 100
1047 ms197560 KiB
#include "fish.h" #include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back using namespace std; typedef pair<ll,ll> pii; typedef pair<ll,pii> ipii; const int MAXN = 5010; const ll INF = 2e15+10; void chmx(auto &a, auto b){ a = max(a, b); } void chmn(auto &a, auto b){ a = min(a, b); } int n, m; ll x[MAXN], y[MAXN], w[MAXN], a[MAXN][MAXN]; ll up[MAXN][MAXN], dw[MAXN][MAXN], pr[MAXN][MAXN]; ll cost(int id, int le, int ri){ if(le > ri) return 0; return pr[id][ri]-pr[id][le-1]; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { n = N; m = M; for(int i=1; i<=m; i++){ x[i] = X[i-1]+1; y[i] = Y[i-1]+1; w[i] = W[i-1]; a[x[i]][y[i]] += w[i]; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) pr[i][j] = pr[i][j-1]+a[i][j]; } for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) dw[i][j] = up[i][j] = -INF; dw[0][0] = up[0][0] = 0; ll ANS = 0; for(int i=1; i<=n; i++){ for(int j=0; j<=n; j++){ for(int k=0; k<=j; k++){ chmx(up[i][j], up[i-1][k] + cost(i-1, k+1, j)); } for(int k=j; k<=n; k++){ chmx(dw[i][j], dw[i-1][k] + cost(i, j+1, k)); } if(i>=2){ ll ba = 0; for(int k=0; k<=n; k++) chmx(ba, max(up[i-2][k], dw[i-2][k])); for(int j=0; j<=n; j++){ chmx(up[i][j], ba + cost(i-1, 1, j)); chmx(dw[i][j], ba + cost(i-1, 1, j)); } } chmx(dw[i][j], up[i][j]); chmx(ANS, up[i][j]); chmx(ANS, dw[i][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...