#include <bits/stdc++.h>
#define m 1000000
#define ll long long
using namespace std;
vector<pair<ll, ll>> best(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> erg;
ll ind = 0, sum = 0;
for (ll i = 0; i < fish.size(); i++)
{
while (steg[ind + 1].first <= fish[i].first)
ind++;
erg.push_back({fish[i].first, steg[ind].second + sum});
sum += fish[i].second;
}
return erg;
}
vector<pair<ll, ll>> collect(vector<pair<ll, ll>> scores, vector<pair<ll, ll>> fish) {
scores.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> next;
ll ind = 0;
for (ll j = 0; j < fish.size(); j++)
{
while(scores[ind + 1].first < fish[j].first)
ind++;
next.push_back({fish[j].first - 1, scores[ind].second});
}
return next;
}
vector<pair<ll, ll>> dp2(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> scores;
ll score = 0, score_steg = 0;
ll ind = 0, ind_steg = 0;
ll h;
while (ind > 0 | ind_steg > 0) {
if (fish[ind].first < steg[ind_steg].first) {
score += fish[ind].second;
h = fish[ind++].first;
} else {
score_steg = steg[ind_steg].second;
h = steg[ind_steg++].first;
}
if (score_steg > score)
score = score_steg;
scores.push_back({h, score});
}
return scores;
}
vector<pair<ll, ll>> dp(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> scores;
ll score = 0, score_steg = 0;
ll ind = fish.size() - 1, ind_steg = steg.size() - 1;
ll h;
while (ind + ind_steg < fish.size() + steg.size() - 2) {
if (fish[ind].first > steg[ind_steg].first) {
score += fish[ind].second;
h = fish[ind--].first;
} else {
score_steg = steg[ind_steg].second;
h = steg[ind_steg--].first;
}
if (score_steg > score)
score = score_steg;
scores.push_back({h, score});
}
return scores;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<ll, ll>>> vert(N);
for (ll i = 0; i < M; i++)
{
vert[X[i]].push_back({Y[i], W[i]});
}
for (ll i = 0; i < N; i++)
{
vert[i].push_back({0, 0});
sort(vert[i].begin(), vert[i].end());
}
vector<pair<ll, ll>> up, down;
for (auto a: vert[0]) {
up.push_back({a.first - 1, 0});
down.push_back({a.first - 1, 0});
}
for (ll i = 0; i < N - 1; i++)
{
vector<pair<ll, ll>> next_up = collect(dp(up, vert[i]), vert[i + 1]);
vector<pair<ll, ll>> next_down = collect(dp2(down, vert[i + 1]), vert[i + 1]);
for (ll j = 0; j < next_down.size(); j++)
{
next_down[j].second = max(next_down[j].second, next_up[j].second);
}
vector<pair<ll, ll>> best_zero = best(down, vert[i + 1]);
for (ll j = 0; j < best_zero.size(); j++)
{
next_up[j].second = max(next_up[j].second, best_zero[j].second);
}
up = next_up;
down = next_down;
assert(up.size() == down.size());
for (int i = 0; i < up.size(); i++)
{
assert(up[i].first == down[i].first);
}
cout << (i + 1) << endl;
for (auto s: down)
cout << s.second << " ";
cout << endl;
for (auto s: up)
cout << s.second << " ";
cout << endl;
}
return max(down.front().second, up.back().second);
}
Compilation message
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > best(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:14:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (ll i = 0; i < fish.size(); i++)
| ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > collect(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:34:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (ll j = 0; j < fish.size(); j++)
| ~~^~~~~~~~~~~~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > dp2(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:54:14: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
54 | while (ind > 0 | ind_steg > 0) {
| ~~~~^~~
fish.cpp: In function 'std::vector<std::pair<long long int, long long int> > dp(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
fish.cpp:80:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while (ind + ind_steg < fish.size() + steg.size() - 2) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:121:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (ll j = 0; j < next_down.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:127:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (ll j = 0; j < best_zero.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int i = 0; i < up.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
30008 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11432 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11432 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
30008 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
