#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<vector<pair<int, int>>> a(n);
for (int i = 0; i < m; i++) a[X[i]].emplace_back(Y[i] + 1, W[i]);
vector<vector<pair<int, ll>>> dp(n), dp2(n), pref(n);
for (int x = 0; x < n; x++) {
sort(a[x].begin(), a[x].end());
a[x].emplace_back(n + 1, 0);
ll sum = 0;
for (auto [y, w]: a[x]) {
sum += w;
pref[x].emplace_back(y, sum);
}
}
auto get = [&](int x, int l, int r) -> ll {
if (l > r) return 0;
int i = lower_bound(pref[x].begin(), pref[x].end(), make_pair(l, 0ll)) - pref[x].begin();
int j = lower_bound(pref[x].begin(), pref[x].end(), make_pair(r + 1, 0ll)) - pref[x].begin() - 1;
if (i > j) return 0;
return pref[x][j].ss - (i > 0 ? pref[x][i - 1].ss : 0ll);
};
for (auto [y, w]: a[0]) dp[0].emplace_back(y - 1, 0);
ll ans = 0;
for (int x = 1; x < n; x++) {
// cout << '\t' << x << endl;
for (int i = 0; i < a[x].size(); i++) {
a[x][i].ff--;
ll mx = 0, mx2 = 0;
for (int j = 0; j < a[x - 1].size(); j++) {
if (dp[x - 1][j].ff <= a[x][i].ff) {
mx = max(mx, dp[x - 1][j].ss + get(x - 1, dp[x - 1][j].ff + 1, a[x][i].ff));
}
if (dp[x - 1][j].ff >= a[x][i].ff) {
mx2 = max(mx, dp[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));
if (j < dp2[x].size()) mx2 = max(mx, dp2[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));
}
}
dp[x].emplace_back(a[x][i].ff, mx);
// cout << i << ' ' << a[x][i].ff << ' ' << dp[x].back().ss << endl;
dp2[x].emplace_back(a[x][i].ff, mx2);
ans = max(ans, max(dp[x].back().ss, dp2[x].back().ss));
a[x][i].ff++;
}
}
return ans;
}
// g++ -o fish -O2 fish.cpp grader.cpp -std=c++17 && .\fish < input.txt > output.txt
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < a[x].size(); i++) {
| ~~^~~~~~~~~~~~~
fish.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int j = 0; j < a[x - 1].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if (j < dp2[x].size()) mx2 = max(mx, dp2[x - 1][j].ss + get(x, a[x][i].ff + 1, dp[x - 1][j].ff));
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
26612 KB |
Output is correct |
| 2 |
Correct |
53 ms |
30156 KB |
Output is correct |
| 3 |
Correct |
21 ms |
22360 KB |
Output is correct |
| 4 |
Correct |
22 ms |
22100 KB |
Output is correct |
| 5 |
Incorrect |
165 ms |
55080 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '89873530379654' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
94 ms |
50216 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
22360 KB |
Output is correct |
| 2 |
Correct |
22 ms |
22360 KB |
Output is correct |
| 3 |
Incorrect |
45 ms |
24660 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '1999989354' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
22360 KB |
Output is correct |
| 2 |
Correct |
22 ms |
22360 KB |
Output is correct |
| 3 |
Incorrect |
45 ms |
24660 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '1999989354' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
26612 KB |
Output is correct |
| 2 |
Correct |
53 ms |
30156 KB |
Output is correct |
| 3 |
Correct |
21 ms |
22360 KB |
Output is correct |
| 4 |
Correct |
22 ms |
22100 KB |
Output is correct |
| 5 |
Incorrect |
165 ms |
55080 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '89873530379654' |
| 6 |
Halted |
0 ms |
0 KB |
- |
