#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long max_weights(int32_t n, int32_t m, vector<int32_t> X, vector<int32_t> Y,
vector<int32_t> W) {
int a[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
a[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
X[i]++; Y[i]++;
a[X[i]][Y[i]] = W[i];
}
int ps[n + 1][n + 1]; // ps[i][j] = a[i][1] + ... + a[i][j]
for (int i = 1; i <= n; i++) {
ps[i][0] = 0;
for (int j = 1; j <= n; j++) {
ps[i][j] = ps[i][j - 1] + a[i][j];
}
}
int dp[2][n + 1][n + 1];
// dp[increasing][pos][height] = max ans from 1 to pos with pos getting height, height must be increasing
for (int i = 0; i <= n; i++) {
dp[0][0][i] = dp[1][0][i] = 0;
dp[0][1][i] = dp[1][1][i] = 0;
}
int cur[n + 1];
function<void(void)> resetcur = [&]() {
for (int i = 0; i <= n; i++) cur[i] = 0;
};
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[0][i][j] = dp[1][i][j] = 0;
}
// Case 0: height of i is 0
resetcur();
dp[0][i][0] = max(dp[0][i - 1][0], dp[1][i - 1][0]);
for (int j = 1; j <= n; j++) {
dp[0][i][0] = max(dp[0][i][0] + a[i][j], max(dp[0][i - 1][j], dp[1][i - 1][j]));
}
dp[1][i][0] = dp[0][i][0];
// Case 1: height of i-1 is 0
// Case 1.1: height of i-2 <= height of i
resetcur();
cur[1] = dp[0][i - 2][1];
for (int j = 2; j <= n; j++) {
cur[j] = max(cur[j - 1], dp[0][i - 2][j]);
}
for (int j = 1; j <= n; j++) {
dp[0][i][j] = max(dp[0][i][j], cur[j] + ps[i][j]);
dp[1][i][j] = max(dp[1][i][j], cur[j] + ps[i][j]);
}
// Case 1.2: height of i-2 >= height of i
resetcur();
cur[n] = dp[0][i - 2][n] + ps[i][n];
for (int j = n - 1; j >= 1; j--) {
cur[j] = max(cur[j + 1], dp[0][i - 2][j] + ps[i][j]);
}
for (int j = 1; j <= n; j++) {
dp[0][i][j] = max(dp[0][i][j], cur[j]);
dp[1][i][j] = max(dp[1][i][j], cur[j]);
}
// Case 2: height of i-1 <= height of i
dp[0][i][1] = max(dp[0][i - 1][1], a[i][1]);
for (int j = 2; j <= n; j++) {
dp[0][i][j] = max(dp[0][i][j - 1] + a[i - 1][j], dp[0][i - 1][j]);
}
// Case 3: height of i-1 >= height of i
dp[1][i][n] = dp[1][i - 1][n];
for (int j = n - 1; j >= 1; j--) {
dp[1][i][j] = max(dp[1][i][j + 1] + a[i][j], dp[1][i - 1][j]);
}
}
int ans = 0;
for (int i = 0; i <= n; i++) {
ans = max(ans, max(dp[0][n][i], dp[1][n][i]));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
963 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: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
914 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 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 |
0 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 |
0 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 |
914 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
963 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
