#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3e2 + 10;
ll col_sm[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N][MAX_N];
ll dp_pref[MAX_N][MAX_N][MAX_N];
ll dp_suff[MAX_N][MAX_N][MAX_N];
ll pref_mx[MAX_N][MAX_N][MAX_N];
ll dpp[MAX_N][MAX_N][MAX_N];
ll f(int r, int c) {
if (r == -1) return 0;
return col_sm[r][c];
}
ll sm(int c, int r1, int r2) {
return f(r2, c) - f(r1 - 1, c);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
col_sm[X[i]][Y[i]] = W[i];
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
col_sm[i][j] += col_sm[i - 1][j];
}
}
//H bardzrutyun => (0, 1, ..., H - 1) bolory vercvac en
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
pref_mx[1][h1][h2] = max(dp[1][h1][h2], pref_mx[1][h1 - 1][h2]);
if (h1 >= h2) {
dp_pref[1][h1][h2] = max(dp_pref[1][h1 - 1][h2], dp[1][h1][h2] - sm(1, h2, h1 - 1));
}
}
}
for (int h1 = N; h1 >= 0; h1--) {
for (int h2 = 0; h2 <= h1; h2++) {
dp_suff[1][h1][h2] = max(dp[1][h1][h2], dp_suff[1][h1 + 1][h2]);
}
}
for (int i = 2; i < N; i++) {
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
if (h1 >= h2) {
//dp[i][h1][h2] = max(dp[i - 1][esim][h1] + sm(i, h2, h1 - 1));
dp[i][h1][h2] = pref_mx[i - 1][N][h1] + sm(i, h2, h1 - 1);
}
else {
//h1 < h2
//if h3 <= h1 < h2
dp[i][h1][h2] = pref_mx[i - 1][h1][h1] + sm(i - 1, h1, h2 - 1);
//if h1 < h2 <= h3
//dp[i][h1][h2] = max(dp[i - 1][h3][h1] - sm(i, h1, h2 - 1))
dp[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i - 1][h2][h1]);
//if h1 < h3 <= h2
dp[i][h1][h2] = max(dp[i][h1][h2], dp_pref[i - 1][h2][h1] + sm(i - 1, h1, h2 - 1));
}
}
}
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
pref_mx[i][h1][h2] = max(dp[i][h1][h2], pref_mx[i][h1 - 1][h2]);
if (h1 >= h2) {
dp_pref[i][h1][h2] = max(dp_pref[i][h1 - 1][h2], dp[i][h1][h2] - sm(i, h2, h1 - 1));
}
}
}
for (int h1 = N; h1 >= 0; h1--) {
for (int h2 = 0; h2 <= h1; h2++) {
dp_suff[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i][h1 + 1][h2]);
}
}
}
ll mx = 0;
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
mx = max(mx, dp[N - 1][h1][h2]);
}
}
return mx;
}
/*
int main() {
cout << max_weights(5, 4, { 0, 1, 4, 3 }, { 2, 1, 4, 3 }, { 5, 2, 1, 3 });
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 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 |
14 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2652 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 |
2652 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 |
2652 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 |
14 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
