Submission #1083867

#TimeUsernameProblemLanguageResultExecution timeMemory
1083867SamueleVidCatfish Farm (IOI22_fish)C++17
18 / 100
1109 ms2097152 KiB
#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]; segment seg_no_ps[N + 5][MAXY + 5]; segment seg_ps[N + 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 ++) { seg_no_ps[i][j] = segment(); seg_ps[i][j] = segment(); } } 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 --) { for (int y = 0; y <= MAXY; y ++) { for (int dx = 0; dx <= MAXY; dx ++) { // 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 = seg_no_ps[i + 1][dx].query(0, 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 = seg_ps[i + 1][dx].query(dx, y) + ps_grid[i + 1][y]; } ll right_of_dx_right_of_y = seg_no_ps[i + 1][dx].query(max(dx, y), MAXY); // 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].update(dx, dp[i][y][dx]); seg_ps[i][y].update(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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...