#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define ll long long
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
ll fish[N][N];
memset(fish, 0, sizeof fish);
for (int i = 0; i < M; i++) {
fish[X[i]][Y[i]] = W[i];
}
ll pfx[N][N+1][2];
memset(pfx, 0, sizeof pfx);
for (int x = 0; x < N; x++) {
for (int y = 1; y <= N; y++) {
ll l = 0;
if (x > 0) {
l = fish[x-1][y-1];
}
ll r = 0;
if (x < N-1) {
r = fish[x+1][y-1];
}
pfx[x][y][0] = pfx[x][y-1][0] + l;
pfx[x][y][1] = pfx[x][y-1][1] + r;
}
}
/*
for (int x = 0; x <= N; x++) {
for (int y = 0; y < N; y++) {
cout << pfx[y][x][0] << ":" << pfx[y][x][1] << " ";
}
cout << endl;
}
*/
ll dp[N][N+1][3];
memset(dp, 0, sizeof dp);
for (int y = 1; y <= N; y++) {
dp[0][y][0] = pfx[0][y][1];
dp[0][y][1] = pfx[0][y][1];
dp[0][y][2] = pfx[0][y][1];
}
for (int x = 1; x < N; x++) {
for (int y = 0; y <= N; y++) {
dp[x][y][0] = pfx[x][y][0] + pfx[x][y][1];
for (int k = 0; k <= N; k++) {
if (x > 2) {
dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][0] + pfx[x][y][0] + pfx[x][y][1]);
dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][1] + pfx[x][y][0] + pfx[x][y][1]);
dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][2] + pfx[x][y][0] + pfx[x][y][1]);
}
if (x > 1) {
ll addend = 0;
if (y > k) {
addend = pfx[x][y][0] - pfx[x][k][0];
}
dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][0] + addend + pfx[x][y][1]);
dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][1] + addend + pfx[x][y][1]);
dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][2] + addend + pfx[x][y][1]);
}
if (x > 0) {
ll addend = 0;
if (y > k) {
addend = pfx[x][y][0] - pfx[x][k][0];
}
dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][0] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][1] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
}
}
}
}
/*
for (int x = 0; x <= N; x++) {
for (int y = 0; y < N; y++) {
cout << dp[y][x] << " ";
}
cout << endl;
}*/
ll best = 0;
for (int x = 0; x < N; x++) {
for (int y = 0; y <= N; y++) {
best = max(dp[x][y][0], best);
best = max(dp[x][y][1], best);
best = max(dp[x][y][2], best);
}
}
return best;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
864 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1154 ms |
2090056 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
841 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
841 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
864 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
