#include <bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int MAXN = 1e5 + 5;
constexpr int PW = 512;
ll sum_tutto(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
ll sum = 0;
for (auto x : W) sum += x;
return sum;
}
ll res_minore_di_due(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
if (N == 2) {
// massimo tra 0 e 1
ll one = 0;
ll zero = 0;
for (int i = 0; i < M; i ++) {
if (X[i] == 0) zero += W[i];
else one += W[i];
}
return max(one, zero);
}
// altrimenti piazza una riga in 2 e poi prendi prefisso maggiore piazzando in 1
ll sum = 0;
for (int i = 0; i < M; i ++) {
if (X[i] == 1) sum += W[i];
}
vector<vector<ll>> pos(2, vector<ll>(N + 5, 0));
for (int i = 0; i < M; i ++) {
pos[X[i]][Y[i]] += W[i];
}
ll best_res = sum;
ll sum_zero = 0;
ll sum_uno = 0;
for (int i = 0; i < N + 5; i ++) {
sum_zero += pos[0][i];
sum_uno += pos[1][i];
best_res = max(best_res, sum - sum_uno + sum_zero);
}
return best_res;
}
ll res_y_zero(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<ll>> dp(2, vector<ll>(N + 5)); // posso prendere a sx o no, posizione
vector<ll> grid(N + 5);
for (int i = 0; i < M; i ++) grid[X[i]] = W[i];
for (int i = N - 1; i >= 0; i --) {
dp[0][i] = dp[1][i + 1];
dp[0][i] = max(dp[0][i], dp[0][i + 1]);
dp[0][i] = max(dp[0][i], dp[0][i + 2] + grid[i + 1]);
dp[0][i] = max(dp[0][i], dp[1][i + 3] + grid[i + 1]);
dp[0][i] = max(dp[0][i], dp[0][i + 3] + grid[i + 1]);
if (i != 0) {
dp[1][i] = dp[1][i + 1];
dp[1][i] = max(dp[1][i], dp[0][i + 1] + grid[i - 1]);
dp[1][i] = max(dp[1][i], dp[0][i + 2] + grid[i - 1] + grid[i + 1]);
dp[1][i] = max(dp[1][i], dp[1][i + 3] + grid[i - 1] + grid[i + 1]);
dp[1][i] = max(dp[1][i], dp[0][i + 3] + grid[i - 1] + grid[i + 1]);
}
}
ll best_res = 0;
for (int i = 0; i <= N; i ++) {
best_res = max(best_res, dp[0][i]);
best_res = max(best_res, dp[1][i]);
}
return best_res;
}
ll cubic(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
// i, quanto lo alzo, quanto era alzato a destra
// int MAXY = min(N, 9);
int MAXY = N;
ll dp[N + 5][MAXY + 5][MAXY + 5];
for (int i = 0; i < N + 5; i ++) {
for (int j = 0; j < MAXY + 5; j ++) {
for (int k = 0; k < MAXY + 5; k ++) {
dp[i][j][k] = 0;
}
}
}
ll grid[N + 5][MAXY + 5];
for (int i = 0; i < N + 5; i ++) {
for (int j = 0; j < MAXY + 5; j ++) {
grid[i][j] = 0;
}
}
for (int i = 0; i < M; i ++) grid[X[i]][Y[i]] = W[i];
ll ps_grid[N + 5][MAXY + 5]; // 1 based per le Y
for (int i = 0; i < N + 5; i ++) {
ps_grid[i][0] = 0;
for (int j = 0; j < MAXY + 4; j ++) {
ps_grid[i][j + 1] = ps_grid[i][j] + grid[i][j];
}
}
for (int i = N - 1; i >= 0; i --) {
for (int y = 0; y <= MAXY; y ++) {
for (int dx = 0; dx <= MAXY; dx ++) {
// quanto mi alzo
for (int dxdx = 0; dxdx <= MAXY; dxdx ++) {
ll preso = -ps_grid[i][min(dx, y)];
if (y > max(dx, dxdx)) {
preso += ps_grid[i + 1][y] - ps_grid[i + 1][max(dx, dxdx)];
}
if (i > 0) {
preso += ps_grid[i - 1][y];
// cout << " e poi si aggiunge a sx " << ps_grid[i - 1][y] << '\n';
}
// cout << "preso : " << preso << '\n';
// cout << "new value : " << dp[i + 1][dx][dxdx] + preso << '\n';
dp[i][y][dx] = max(dp[i][y][dx], dp[i + 1][dx][dxdx] + preso);
}
}
}
}
ll res = 0;
for (int i = 0; i < N; i ++) {
for (int y = 0; y < MAXY; y ++) {
for (int dx = 0; dx < MAXY; dx ++) {
res = max(res, dp[i][y][dx]);
}
}
}
return res;
}
struct segment {
vector<ll> seg;
segment() {
seg.assign(2 * PW, 0);
}
void update(int x, ll d) {
x += PW;
while (x >= 1) {
seg[x] = max(seg[x], d);
x /= 2;
}
}
ll query(int l, int r) {
l += PW; r += PW;
ll res = 0;
while (l <= r) {
if (l % 2 == 1) {
res = max(res, seg[l]);
l ++;
}
if (r % 2 == 0) {
res = max(res, seg[r]);
r --;
}
l /= 2; r /= 2;
}
return res;
}
};
ll cubic_seg(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
// i, quanto lo alzo, quanto era alzato a destra
// int MAXY = min(N, 9);
int MAXY = N;
ll dp[N + 5][MAXY + 5][MAXY + 5];
ll seg_no_ps[N + 5][MAXY + 5][MAXY + 5];
ll seg_ps[N + 5][MAXY + 5][MAXY + 5];
for (int i = 0; i < N + 5; i ++) {
for (int j = 0; j < MAXY + 5; j ++) {
for (int k = 0; k < MAXY + 5; k ++) {
dp[i][j][k] = 0;
}
}
}
for (int i = 0; i < N + 5; i ++) {
for (int j = 0; j < MAXY + 5; j ++) {
for (int k = 0; k < MAXY + 5; k ++) {
seg_no_ps[i][j][k] = 0;
seg_ps[i][j][k] = 0;
}
}
}
ll grid[N + 5][MAXY + 5];
for (int i = 0; i < N + 5; i ++) {
for (int j = 0; j < MAXY + 5; j ++) {
grid[i][j] = 0;
}
}
for (int i = 0; i < M; i ++) grid[X[i]][Y[i]] = W[i];
ll ps_grid[N + 5][MAXY + 5]; // 1 based per le Y
for (int i = 0; i < N + 5; i ++) {
ps_grid[i][0] = 0;
for (int j = 0; j < MAXY + 4; j ++) {
ps_grid[i][j + 1] = ps_grid[i][j] + grid[i][j];
}
}
// cout << "N, MAXY : " << N << " " << MAXY << '\n';
// cout << "grid : " << '\n';
// for (int i = 0; i < N + 5; i ++) {
// for (int j = 0; j < MAXY + 5; j ++) {
// cout << grid[i][j] << " ";
// }
// cout << '\n';
// }
// cout << "ps_grid " << '\n';
// for (int i = 0; i < N + 5; i ++) {
// for (int j = 0; j < MAXY + 5; j ++) {
// cout << ps_grid[i][j] << " ";
// }
// cout << '\n';
// }
for (int i = N - 1; i >= 0; i --) {
vector<vector<ll>> curr_right_of_dx_right_of_y(MAXY + 1, vector<ll>(MAXY + 1));
for (int dx = 0; dx <= MAXY; dx ++) {
curr_right_of_dx_right_of_y[dx][MAXY] = seg_no_ps[i + 1][dx][MAXY];
for (int i = MAXY - 1; i >= 0; i --) {
curr_right_of_dx_right_of_y[dx][i] = max(
curr_right_of_dx_right_of_y[dx][i + 1], seg_no_ps[i + 1][dx][i]
);
}
}
vector<vector<ll>> curr_left_of_dx(MAXY + 1, vector<ll>(MAXY + 1));
for (int dx = 0; dx <= MAXY; dx ++) {
curr_left_of_dx[dx][0] = seg_no_ps[i + 1][dx][0];
for (int i = 1; i <= MAXY; i ++) {
curr_left_of_dx[dx][i] = max(
curr_left_of_dx[dx][i - 1], seg_no_ps[i + 1][dx][i]
);
}
}
vector<vector<ll>> curr_right_of_dx_left_of_y(MAXY + 1, vector<ll>(MAXY + 1));
for (int dx = 0; dx <= MAXY; dx ++) {
curr_right_of_dx_left_of_y[dx][dx] = seg_ps[i + 1][dx][dx];
for (int i = dx + 1; i <= MAXY; i ++) {
curr_right_of_dx_left_of_y[dx][i] = max(
curr_right_of_dx_left_of_y[dx][i - 1], seg_ps[i + 1][dx][i]
);
}
}
for (int y = 0; y <= MAXY; y ++) {
for (int dx = 0; dx <= MAXY; dx ++) {
// cout << "i, y, dx : " << i << " " << y << " " << dx << '\n';
// cout << "---- i, y, dx : " << i << " " << y << " " << dx << '\n';
ll preso = -ps_grid[i][min(dx, y)];
if (i > 0) preso += ps_grid[i - 1][y];
// cout << "preso : " << preso << '\n';
// cout << "vedo quelli " << i + 1 << " " << dx << " : " << '\n';
// for (auto x : seg_no_ps[i + 1][dx].seg) cout << x << " ";
// cout << '\n';
// for (auto x : seg_ps[i + 1][dx].seg) cout << x << " ";
// cout << '\n';
// dxdx a sinistra di dx;
ll left_of_dx = curr_left_of_dx[dx][dx] + ps_grid[i + 1][max(y, dx)] - ps_grid[i + 1][dx];
// cout << "reale massimo no ps da 0 a " << dx << " : " << seg_no_ps[i + 1][dx].query(0, dx) << '\n';
// dxdx a destra di dx;
ll right_of_dx_left_of_y = 0;
if (y > dx) {
right_of_dx_left_of_y = curr_right_of_dx_left_of_y[dx][y] + ps_grid[i + 1][y];
}
ll right_of_dx_right_of_y = curr_right_of_dx_right_of_y[dx][max(dx, y)];
// cout << "left_of_dx -> " << left_of_dx << '\n';
// cout << "right_of_dx_left_of_y -> " << right_of_dx_left_of_y << '\n';
// cout << "right_of_dx_right_of_y -> " << right_of_dx_right_of_y << '\n';
dp[i][y][dx] = max(dp[i][y][dx], left_of_dx + preso);
dp[i][y][dx] = max(dp[i][y][dx], right_of_dx_left_of_y + preso);
dp[i][y][dx] = max(dp[i][y][dx], right_of_dx_right_of_y + preso);
// cout << "aggiungo nei seg no ps " << i << ", " << y << " a pos " << dx << " : " << dp[i][y][dx] << " e nei seg ps " << dp[i][y][dx] - ps_grid[i][dx] << '\n';
seg_no_ps[i][y][dx] = dp[i][y][dx];
seg_ps[i][y][dx] = dp[i][y][dx] - ps_grid[i][dx];
}
}
}
ll res = 0;
for (int i = 0; i < N; i ++) {
for (int y = 0; y < MAXY; y ++) {
for (int dx = 0; dx < MAXY; dx ++) {
res = max(res, dp[i][y][dx]);
}
}
}
return res;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
bool all_even = 1;
for (auto x : X) if (x % 2) all_even = 0;
if (all_even) return sum_tutto(N, M, X, Y, W);
bool minore_di_due = 1;
for (auto x : X) if (x >= 2) minore_di_due = 0;
if (minore_di_due) return res_minore_di_due(N, M, X, Y, W);
bool y_zero = 1;
for (auto y : Y) if (y > 0) y_zero = 0;
if (y_zero) return res_y_zero(N, M, X, Y, W);
return cubic_seg(N, M, X, Y, W);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
58 ms |
17240 KB |
Output is correct |
| 6 |
Correct |
62 ms |
17476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
44 ms |
10832 KB |
Output is correct |
| 3 |
Correct |
40 ms |
13144 KB |
Output is correct |
| 4 |
Correct |
16 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
18 ms |
5700 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
18 ms |
6748 KB |
Output is correct |
| 13 |
Correct |
21 ms |
7852 KB |
Output is correct |
| 14 |
Correct |
18 ms |
6632 KB |
Output is correct |
| 15 |
Correct |
18 ms |
7516 KB |
Output is correct |
| 16 |
Correct |
19 ms |
6740 KB |
Output is correct |
| 17 |
Correct |
20 ms |
7376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
5276 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
20 ms |
7876 KB |
Output is correct |
| 6 |
Correct |
17 ms |
7260 KB |
Output is correct |
| 7 |
Correct |
20 ms |
7856 KB |
Output is correct |
| 8 |
Correct |
20 ms |
7772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '7', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '7', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '7', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
5276 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
20 ms |
7876 KB |
Output is correct |
| 6 |
Correct |
17 ms |
7260 KB |
Output is correct |
| 7 |
Correct |
20 ms |
7856 KB |
Output is correct |
| 8 |
Correct |
20 ms |
7772 KB |
Output is correct |
| 9 |
Runtime error |
977 ms |
2097152 KB |
Execution killed with signal 9 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
58 ms |
17240 KB |
Output is correct |
| 6 |
Correct |
62 ms |
17476 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
44 ms |
10832 KB |
Output is correct |
| 9 |
Correct |
40 ms |
13144 KB |
Output is correct |
| 10 |
Correct |
16 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
18 ms |
5700 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
18 ms |
6748 KB |
Output is correct |
| 19 |
Correct |
21 ms |
7852 KB |
Output is correct |
| 20 |
Correct |
18 ms |
6632 KB |
Output is correct |
| 21 |
Correct |
18 ms |
7516 KB |
Output is correct |
| 22 |
Correct |
19 ms |
6740 KB |
Output is correct |
| 23 |
Correct |
20 ms |
7376 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 26 |
Correct |
14 ms |
5276 KB |
Output is correct |
| 27 |
Correct |
9 ms |
4700 KB |
Output is correct |
| 28 |
Correct |
20 ms |
7876 KB |
Output is correct |
| 29 |
Correct |
17 ms |
7260 KB |
Output is correct |
| 30 |
Correct |
20 ms |
7856 KB |
Output is correct |
| 31 |
Correct |
20 ms |
7772 KB |
Output is correct |
| 32 |
Correct |
1 ms |
348 KB |
Output is correct |
| 33 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '7', found: '5' |
| 34 |
Halted |
0 ms |
0 KB |
- |
