Submission #1218173

#TimeUsernameProblemLanguageResultExecution timeMemory
1218173vaneaCatfish Farm (IOI22_fish)C++20
0 / 100
954 ms2162688 KiB
#include <bits/stdc++.h> #include "fish.h" using namespace std; using ll = long long; ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { vector<vector<ll>> pref(N+1, vector<ll>(N+1, 0)); for(int i = 0; i < M; i++) { pref[X[i]][Y[i]+1] += W[i]; } for(int i = 0; i < N; i++) { for(int j = 1; j <= N; j++) { pref[i][j] += pref[i][j-1]; } } ll dp[(int)N][N+1][2]; memset(dp, 0, sizeof dp); ll ans = 0; for(int i = 1; i < N; i++) { for(int j = 0; j <= N; j++) { for(int k = 0; k <= N; k++) { dp[i][j][0] = max({dp[i][j][0], max(dp[i-1][k][1], dp[i-1][k][0]) + max(0LL, pref[i][k] - pref[i][j])}); dp[i][j][1] = max({dp[i][j][1], max(dp[i-1][k][0], dp[i-1][k][1]) + max(0LL, pref[i-1][j]-pref[i-1][k])}); } } } for(int i = 0; i <= N; i++) { ans = max({ans, dp[N-1][i][0], dp[N-1][i][1]}); } 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...