Submission #1209374

#TimeUsernameProblemLanguageResultExecution timeMemory
1209374stdfloatCatfish Farm (IOI22_fish)C++20
0 / 100
959 ms2162688 KiB
#include <bits/stdc++.h> #include "fish.h" // #include "grader.cpp" 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>> p(n + 1, vector<ll>(n + 1)); for (int i = 0; i < M; i++) p[++X[i]][++Y[i]] = W[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) p[i][j] += p[i][j - 1]; } vector<vector<ll>> dp(n + 1, vector<ll>(n + 1)), mx = dp; for (int i = 2; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= n; k++) { if (k < j) dp[i][j] = max(dp[i][j], mx[i - 2][k] + p[i - 1][j] - p[i - 1][k]); else dp[i][j] = max(dp[i][j], dp[i - 1][k] + p[i][k] - p[i][j]); } } for (int j = 1; j <= n; j++) mx[i][j] = max(mx[i][j - 1], dp[i][j]); } return *max_element(dp[n].begin(), dp[n].end()); }
#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...