#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<long long>> dp;
vector<vector<long long>> nxt;
vector<vector<long long>> pre;
vector<vector<pair<int, int>>> in_col;
long long bt(int col, bool f) {
if (col == n) {
return 0;
}
long long& ret = dp[col][f];
if (ret != -1) {
return ret;
}
ret = 0;
int sz = in_col[col].size();
if (!f) {//I'm not taking from the one behind me -> the one in front of me is bigger than me & the one behind me is not a full tower so he's taking from me
long long s = 0;
for (int i = 0; i < sz - 1; ++i) {//take from the next one and give the previous one
long long w = s;
if (col > 0) {
w += pre[col][i];
}
ret = max(ret, bt(col + 1, 0) + w);
s -= in_col[col][i].second;
}
if (col < n - 1) {
s = nxt[col][sz - 1];
}
ret = max(ret, bt(col + 1, 1) + s);//end the sequence. (build a full tower)
} else {//I'm taking from the one behind me -> the one next either takes from me or I don't build anything (subtract me and add the guy next)
long long s = 0;
for (int i = 1; i < sz; ++i) {
s -= in_col[col][i - 1].second;
long long w = s;
if (col < n - 1) {
w += nxt[col][i];
}
ret = max(ret, bt(col + 1, 1) + w);
}
ret = max(ret, bt(col + 1, 0));//end the sequence (don't build)
}
return ret;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
in_col.resize(N);
for (int i = 0; i < M; ++i) {
in_col[X[i]].push_back({Y[i], W[i]});
}
for (int i = 0; i < N; ++i) {
sort(in_col[i].begin(), in_col[i].end());
in_col[i].push_back({N, 0});
}
pre.resize(N);
for (int col = 1; col < N; ++col) {
pre[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
sum += in_col[col - 1][ptr].second;
ptr++;
}
pre[col][i] = sum;
}
}
nxt.resize(N);
for (int col = 0; col < N - 1; ++col) {
nxt[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
sum += in_col[col + 1][ptr].second;
ptr++;
}
nxt[col][i] = sum;
}
}
dp.resize(N);
for (int i = 0; i < N; ++i) {
dp[i].assign(2, -1);
}
long long ans = bt(0, 0);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
32964 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 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 |
Incorrect |
30 ms |
31580 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 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 |
344 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 |
344 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 |
30 ms |
31580 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
32964 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
