#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) {
int n = N, m = M;
vector<vector<int>> c(9, vector<int>(n+1, 0));
vector<vector<vector<int>>> dp(9, vector<vector<int>>(n+1, vector<int>(2, 0))); // 0 is increasing, 1 is decreasing, increasing can go to decreasing, decreasing cant go to increasing if next to eachother
for (int i = 0; i < m; i++) {
c[Y[i]+1][X[i]] = W[i];
}
for (int j = 1; j < n; j++) {
int v = 0;
dp[0][j][0] = max(dp[0][j][0], dp[0][j-1][0]);
for (int i = 1; i < 9; i++) {
v += c[i][j];
dp[0][j][0] = max(dp[0][j][0], dp[i][j-1][0]+v);
dp[0][j][0] = max(dp[0][j][0], dp[i][j-1][1]+v);
}
for (int i = 1; i < 9; i++) {
for (int a = i; a < 9; a++) {
v = 0;
for (int b = i+1; b <= a; b++) {
v += c[b][j];
}
dp[i][j][1] = max(dp[i][j][1], dp[a][j-1][0]+v);
dp[i][j][1] = max(dp[i][j][1], dp[a][j-1][1]+v);
}
for (int a = 1; a <= i; a++) {
v = 0;
for (int b = a+1; b <= i; b++) {
v += c[b][j-1];
}
dp[i][j][0] = max(dp[i][j][0], dp[a][j-1][0]+v);
}
}
if (j == 1) {
v = 0;
for (int i = 1; i < 9; i++) {
v += c[i][j-1];
dp[i][j][0] = max(dp[i][j][0], dp[0][j-1][0]+v);
dp[i][j][1] = max(dp[i][j][1], dp[0][j-1][0]+v);
}
}
if (j-2 >= 0) {
v = 0;
for (int i = 1; i < 9; i++) {
v += c[i][j-1];
dp[i][j][0] = max(dp[i][j][0], dp[0][j-2][0]+v);
dp[i][j][1] = max(dp[i][j][1], dp[0][j-2][0]+v);
}
for (int i = 1; i < 9; i++) {
v = 0;
for (int h = 1; h <= i; h++) {
v += c[h][j-1];
}
for (int h = 1; h <= i; h++) {
dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][0]+v);
dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][1]+v);
}
for (int h = i+1; h < 9; h++) {
v += c[h][j];
dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][0]+v);
dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][1]+v);
}
}
}
}
int ans = 0;
for (int i = 0; i < 9; i++) {
ans = max(ans, dp[i][n-1][0]);
ans = max(ans, dp[i][n-1][1]);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
93 ms |
114256 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
111 ms |
119500 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
62144 KB |
Output is correct |
2 |
Correct |
95 ms |
62208 KB |
Output is correct |
3 |
Correct |
104 ms |
58216 KB |
Output is correct |
4 |
Correct |
95 ms |
63564 KB |
Output is correct |
5 |
Correct |
109 ms |
66192 KB |
Output is correct |
6 |
Correct |
107 ms |
65544 KB |
Output is correct |
7 |
Correct |
105 ms |
66044 KB |
Output is correct |
8 |
Correct |
110 ms |
66108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '223739526227' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '223739526227' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '223739526227' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
62144 KB |
Output is correct |
2 |
Correct |
95 ms |
62208 KB |
Output is correct |
3 |
Correct |
104 ms |
58216 KB |
Output is correct |
4 |
Correct |
95 ms |
63564 KB |
Output is correct |
5 |
Correct |
109 ms |
66192 KB |
Output is correct |
6 |
Correct |
107 ms |
65544 KB |
Output is correct |
7 |
Correct |
105 ms |
66044 KB |
Output is correct |
8 |
Correct |
110 ms |
66108 KB |
Output is correct |
9 |
Runtime error |
112 ms |
127256 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
93 ms |
114256 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |