# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1123292 | sunboi | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y,
vector<int> W) {
/*vector<pair<int, int>> a(M);
for (int i = 0; i < M; i++){
a[i] = {X[i], Y[i]};
}*/
vector<vector<int>> pref(N, vector<int> pref(N + 1));
for (int i = 0; i < M; i++){
pref[X[i]][Y[i]] += W[i];
}
for (int i = 0; i < N; i++){
for (int j = 1; j <= N; j++){
pref[i][j] += pref[i][j - 1];
}
}
vector<vector<int>> dp(N, vector<int> pref(N + 1));
int ans = 0;
for (int i = 1; i < N; i++){
for (int prev = 0; prev <= N; prev++){
for (int j = 0; j <= N; j++){
int cogemos = 0;
if (prev > j){
cogemos = pref[i][prev] - pref[i][j];
}else{
cogemos = pref[i - 1][j] - pref[i][prev];
}
dp[i][j] = max(dp[i][j], dp[i - 1][prev] + cogemos);
}
}
}
for (int i = 0; i <= N; i++) ans = max(ans, dp[N - 1][i]);
return ans;
}