#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "fish.h"
int MAX_R = 10;
int MAX_C = 10;
ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
MAX_R = min(N, 3);
MAX_C = N;
vector<vi> a(N, vi(N, 0));
for (int i = 0; i < M; i++) {
a[X_g[i]][Y_g[i]] += W_g[i];
}
/* cout<<"a: "<<endl;
for (vi v : a) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
vector<vi> pfs(MAX_R, vi(MAX_C + 1, 0)); // vertical pfs
for (int i = 0; i < MAX_R; i++) {
pfs[i][0] = 0;
for (int j = 1; j <= MAX_C; j++) {
pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
}
}
/* cout<<"pfs: "<<endl;
for (vi v : pfs) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
vector<vi> dp(MAX_R + 1, vi(MAX_C + 1, 0));
// dp[i][j]: max sum till i, exclusive; j = pier height
// prefix max / sum to optimize?
for (int i = 1; i <= MAX_C; i++) {
dp[0][i] = -1e18;
}
for (int i = 1; i <= MAX_R; i++) {
// a[i - 1] is empty
for (int j = 0; j <= MAX_C; j++) {
dp[i][0] = max(dp[i][0], dp[i - 1][j] + (pfs[i - 1][j] - pfs[i - 1][0]));
}
for (int j = 1; j <= MAX_C; j++) { // fill up to j
// try all right filled combinations
if (i == 1) { // first coln
dp[i][j] = 0;
}
else if (i == 2) {
for (int k = 0; k <= j; k++) { // left is up to k <= j
dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 2][j] - pfs[i - 2][k]));
}
for (int k = j + 1; k <= MAX_C; k++) { // left is up to k > j
dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
}
}
else { // i >= 3
for (int k = 0; k <= j; k++) { // left is up to k <= j
for (int l = 0; l <= MAX_C; l++) { // 2x left is up to l
if (l >= j) { // nothing added
dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][l] - pfs[i - 2][k]));
}
else if (l >= k) {
dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][j] - pfs[i - 2][k]));
}
else {
dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 3][k] - pfs[i - 3][l]) + (pfs[i - 2][j] - pfs[i - 2][k]));
}
}
}
for (int k = j + 1; k <= MAX_C; k++) { // left is up to k > j
dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
}
}
}
}
/* cout<<"dp: "<<endl;
for (vi v : dp) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
ll ans = 0;
for (int i = 0; i <= MAX_C; i++) {
ans = max(ans, dp[MAX_R][i]);
}
return ans;
}
// can extend subtask 3 logic for polynomial soln
// optimize with segtree range max if needed
// if have poly soln, can get subtasks 2 and 4 right away by changing bounds
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
636 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
645 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
638 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
638 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
636 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
