#include <bits/stdc++.h>
long long max_weights(int n, int m, std::vector <int> _x, std::vector <int> _y, std::vector <int> _w) {
std::vector <std::vector <std::pair <int, int>>> of(n);
for (int i = 0; i < m; i++) {
of[_x[i]].emplace_back(_y[i], _w[i]);
}
for (int i = 0; i < n; i++) {
of[i].emplace_back(0, 0);
of[i].emplace_back(n, 0);
std::sort(of[i].begin(), of[i].end());
if (of[i][1].second) {
of[i].erase(of[i].begin());
}
}
std::vector <std::vector <std::vector <long long>>> dp(n, std::vector <std::vector <long long>> (3));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
dp[i][j].resize(of[i].size());
}
}
std::vector <std::vector <long long>> pre(n);
for (int i = 0; i < n; i++) {
pre[i].resize(of[i].size());
pre[i][0] = of[i][0].second;
for (int j = 1; j < (int) of[i].size(); j++) {
pre[i][j] = pre[i][j - 1] + of[i][j].second;
}
}
dp[0][0].assign(dp[0][0].size(), 0);
for (int nxt = 0, j = 1; j < (int) of[0].size(); j++) {
while (nxt + 1 < (int) of[1].size() && of[1][nxt + 1].first < of[0][j].first) {
nxt++;
}
dp[0][1][j] = pre[1][nxt];
}
for (int i = 1; i < n; i++) {
std::vector <long long> pre_mx0(dp[i - 1][0].size());
pre_mx0[0] = dp[i - 1][0][0];
for (int j = 1; j < (int) dp[i - 1][0].size(); j++) {
pre_mx0[j] = std::max(dp[i - 1][0][j], pre_mx0[j - 1]);
}
std::vector <long long> suf_mx[2];
for (int k = 0; k <= 1; k++) {
suf_mx[k].resize(dp[i - 1][k + 1].size());
suf_mx[k].back() = dp[i - 1][k + 1].back();
for (int j = (int) dp[i - 1][k + 1].size() - 2; j >= 0; j--) {
suf_mx[k][j] = std::max(dp[i - 1][k + 1][j], suf_mx[k][j + 1]);
}
}
std::vector <long long> psuf_mx[2];
std::vector <long long> ppre_mx[2];
for (int k = 0; k <= 1; k++) {
psuf_mx[k].resize(i > 1 ? dp[i - 2][k + 1].size() : 1, 0);
if (i > 1) {
ppre_mx[k].resize(dp[i - 2][k + 1].size());
for (int ptr = 0, j = 0; j < (int) dp[i - 2][k + 1].size(); j++) {
while (ptr + 1 < (int) of[i - 1].size() && of[i - 1][ptr + 1].first < of[i - 2][j].first) {
ptr++;
}
ppre_mx[k][j] = dp[i - 2][k + 1][j] - pre[i - 1][ptr];
if (j) {
ppre_mx[k][j] = std::max(ppre_mx[k][j], ppre_mx[k][j - 1]);
}
}
psuf_mx[k].back() = dp[i - 2][k + 1].back();
for (int j = (int) dp[i - 2][k + 1].size() - 2; j >= 0; j--) {
psuf_mx[k][j] = std::max(dp[i - 2][k + 1][j], psuf_mx[k][j + 1]);
}
}
}
dp[i][0][0] = dp[i][0][0] = std::max({ pre_mx0[0], psuf_mx[0][0], psuf_mx[1][0] });
dp[i][1][0] = pre_mx0[0];
dp[i][2][0] = std::max(suf_mx[0][0], suf_mx[1][0]);
if (i > 1) {
for (int prv = 0, nxt = 0, nnxt = 0, j = 0; j < (int) dp[i][0].size(); j++) {
while (prv + 1 < (int) of[i - 2].size() && of[i - 2][prv + 1].first < of[i][j].first) {
prv++;
}
while (nxt + 1 < (int) of[i - 1].size() && of[i - 1][nxt + 1].first < of[i][j].first) {
nxt++;
}
while (i + 1 < n && nnxt + 1 < (int) of[i + 1].size() && of[i + 1][nnxt + 1].first < of[i][j].first) {
nnxt++;
}
dp[i][0][j] = std::max({ dp[i][0][j], ppre_mx[0][prv] + pre[i - 1][nxt],
ppre_mx[1][prv] + pre[i - 1][nxt], psuf_mx[0][prv], psuf_mx[1][prv] });
dp[i][1][j] = std::max(dp[i][1][j], std::max({ ppre_mx[0][prv] + pre[i - 1][nxt],
ppre_mx[1][prv] + pre[i - 1][nxt], psuf_mx[0][prv], psuf_mx[1][prv] }) + (i + 1 < n ? pre[i + 1][nnxt] : 0LL));
}
}
for (int prv = 0, nxt = 0, j = 1; j < (int) of[i].size(); j++) {
while (prv + 1 < (int) of[i - 1].size() && of[i - 1][prv + 1].first < of[i][j].first) {
prv++;
}
while (i + 1 < n && nxt + 1 < (int) of[i + 1].size() && of[i + 1][nxt + 1].first < of[i][j].first) {
nxt++;
}
dp[i][0][j] = std::max(dp[i][0][j], pre_mx0[prv] + pre[i - 1][prv] - pre[i][j - 1]);
dp[i][1][j] = std::max(dp[i][1][j], pre_mx0[prv] + pre[i - 1][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL));
dp[i][2][j] = std::max(
suf_mx[0][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL) - pre[i][j - 1],
suf_mx[1][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL) - pre[i][j - 1]);
}
}
long long ans = 0;
for (int k = 0; k < 3; k++) {
for (long long x : dp[n - 1][k]) {
ans = std::max(ans, x);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
35288 KB |
Output is correct |
| 2 |
Correct |
119 ms |
40208 KB |
Output is correct |
| 3 |
Correct |
77 ms |
30812 KB |
Output is correct |
| 4 |
Correct |
89 ms |
30796 KB |
Output is correct |
| 5 |
Correct |
209 ms |
52548 KB |
Output is correct |
| 6 |
Correct |
229 ms |
48808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 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 |
Correct |
81 ms |
30764 KB |
Output is correct |
| 2 |
Correct |
97 ms |
30760 KB |
Output is correct |
| 3 |
Correct |
110 ms |
29944 KB |
Output is correct |
| 4 |
Correct |
96 ms |
32348 KB |
Output is correct |
| 5 |
Correct |
123 ms |
35260 KB |
Output is correct |
| 6 |
Correct |
160 ms |
35160 KB |
Output is correct |
| 7 |
Correct |
126 ms |
35180 KB |
Output is correct |
| 8 |
Correct |
124 ms |
35284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 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 |
212 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 |
212 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 |
Correct |
81 ms |
30764 KB |
Output is correct |
| 2 |
Correct |
97 ms |
30760 KB |
Output is correct |
| 3 |
Correct |
110 ms |
29944 KB |
Output is correct |
| 4 |
Correct |
96 ms |
32348 KB |
Output is correct |
| 5 |
Correct |
123 ms |
35260 KB |
Output is correct |
| 6 |
Correct |
160 ms |
35160 KB |
Output is correct |
| 7 |
Correct |
126 ms |
35180 KB |
Output is correct |
| 8 |
Correct |
124 ms |
35284 KB |
Output is correct |
| 9 |
Incorrect |
127 ms |
35160 KB |
1st lines differ - on the 1st token, expected: '99999', found: '66666' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
35288 KB |
Output is correct |
| 2 |
Correct |
119 ms |
40208 KB |
Output is correct |
| 3 |
Correct |
77 ms |
30812 KB |
Output is correct |
| 4 |
Correct |
89 ms |
30796 KB |
Output is correct |
| 5 |
Correct |
209 ms |
52548 KB |
Output is correct |
| 6 |
Correct |
229 ms |
48808 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
