#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300;
const int kUp = 0, kDown = 1;
const long long kInf = 4e18;
long long psum[kMaxN][kMaxN+1];
long long dp[kMaxN][kMaxN+1][2];
int N;
long long solve(int col, int y_bef, int mode) {
if (col >= N) {
return 0;
}
long long &ret = dp[col][y_bef][mode];
if (ret != -1) {
return ret;
}
ret = -kInf;
for (int i = 1 ; i <= N ; i++) {
long long add = 0;
if (col+1 < N) add += psum[col+1][i];
if (col > 0) add -= psum[col][min(i, y_bef)];
if (col > 0 && i > y_bef) add += (psum[col-1][i] - psum[col-1][y_bef]);
if (mode == kUp) {
ret = max(ret, add + solve(col+1, i, i >= y_bef ? kUp : kDown));
}
if (mode == kDown) {
if (i <= y_bef) ret = max(ret, add + solve(col+1, i, kDown));
else break;
}
}
// if we turn this into 0
ret = max(ret, solve(col+2, 0, kUp));
if (y_bef == 0) {
ret = max(ret, solve(col+1, 0, kUp));
}
if (col+2 <= N) {
// set for col+1
for (int i = 1 ; i <= N ; i++) {
long long add = 0;
if (col+2 < N) add += psum[col+2][i];
if (col+1 < N) add += (psum[col][max(i, y_bef)] - psum[col][y_bef]);
ret = max(ret, add + solve(col+2, i, kUp));
}
}
return ret;
}
long long max_weights(int _N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
N = _N;
for (int i = 0 ; i < M ; i++) {
psum[X[i]][Y[i]+1] += W[i]; // increment y by one to ease our life
}
for (int i = 0 ; i < N ; i++) {
for (int j = 1 ; j <= N ; j++) {
psum[i][j] += psum[i][j-1];
}
}
memset(dp, -1, sizeof dp);
long long ret = solve(0, 0, kUp);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
6984 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1620 KB |
Output is correct |
2 |
Runtime error |
77 ms |
12188 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
1748 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1620 KB |
Output is correct |
2 |
Correct |
2 ms |
1620 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
2 ms |
1620 KB |
Output is correct |
5 |
Correct |
2 ms |
1620 KB |
Output is correct |
6 |
Correct |
2 ms |
1620 KB |
Output is correct |
7 |
Correct |
1 ms |
1620 KB |
Output is correct |
8 |
Correct |
1 ms |
1620 KB |
Output is correct |
9 |
Correct |
124 ms |
2080 KB |
Output is correct |
10 |
Execution timed out |
1008 ms |
2536 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1620 KB |
Output is correct |
2 |
Correct |
2 ms |
1620 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
2 ms |
1620 KB |
Output is correct |
5 |
Correct |
2 ms |
1620 KB |
Output is correct |
6 |
Correct |
2 ms |
1620 KB |
Output is correct |
7 |
Correct |
1 ms |
1620 KB |
Output is correct |
8 |
Correct |
1 ms |
1620 KB |
Output is correct |
9 |
Correct |
124 ms |
2080 KB |
Output is correct |
10 |
Execution timed out |
1008 ms |
2536 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1620 KB |
Output is correct |
2 |
Correct |
2 ms |
1620 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
2 ms |
1620 KB |
Output is correct |
5 |
Correct |
2 ms |
1620 KB |
Output is correct |
6 |
Correct |
2 ms |
1620 KB |
Output is correct |
7 |
Correct |
1 ms |
1620 KB |
Output is correct |
8 |
Correct |
1 ms |
1620 KB |
Output is correct |
9 |
Correct |
124 ms |
2080 KB |
Output is correct |
10 |
Execution timed out |
1008 ms |
2536 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
1748 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
6984 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |