# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123291 | sunboi | 메기 농장 (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int64 max_weights(int N, int M, int[] X, int[] Y, 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;
}