#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
enum {
UP = 0,
DOWN = 1
};
ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int, int>>> fishes(N);
F(i, 0, M) fishes[X[i]].push_back(make_pair(Y[i], i));
ll two_columns_back = 0;
vector<pl> up, down; // stores [ypos, dpvalue] of prev state
vector<vl> dp(M, vl(2, -1e18)); // dp[fish index][type]
F(x, 0, N) {
sort(fishes[x].begin(), fishes[x].end());
if (x > 0) { // w/o this check, we allow placing piers to index -1 which is no bueno
ll max_down = 0;
FD(j, ll(fishes[x].size()) - 1, -1) {
auto [y, i] = fishes[x][j];
while (down.size() > 0 && down.back().K > y) {
max_down = max(max_down, down.back().V);
down.pop_back();
}
auto &ret = dp[i][DOWN];
ret = max(two_columns_back, max_down);
// taking cummulative max
if (j + 1 < fishes[x].size()) {
ret = max(ret, dp[fishes[x][j + 1].V][DOWN]);
}
ret += W[i];
}
}
ll max_up = 0;
for (int j = 0; j < fishes[x].size(); ++j) {
auto [y, i] = fishes[x][j];
while (up.size() > 0 && up.back().K < y) {
max_up = max(max_up, up.back().V);
up.pop_back();
}
ll &ret = dp[i][UP];
ret = max(two_columns_back, max_up);
if (j > 0) {
ret = max(ret, dp[fishes[x][j - 1].V][UP] + W[i]);
}
ret += W[i];
}
//
if (x >= 1) for (auto [y, i] : fishes[x - 1]) {
two_columns_back = max({two_columns_back, dp[i][UP], dp[i][DOWN]});
}
down.clear();
for (auto [y, i]: fishes[x]) down.emplace_back(y, dp[i][DOWN]);
up.clear();
for (auto [y, i]: fishes[x]) up.emplace_back(y, dp[i][UP]);
reverse(A(up));
}
ll answer = 0;
F(i, 0, M) {
answer = max(answer, dp[i][DOWN]);
if (X[i] + 1 < N) answer = max(answer, dp[i][UP]);
}
return answer;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:58:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (j + 1 < fishes[x].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j = 0; j < fishes[x].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
14760 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '80626321775495' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
89 ms |
22344 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '81208111438092' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2736 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
9044 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
432 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '285724051047' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
432 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '285724051047' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
432 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '285724051047' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2736 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
9044 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
14760 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '80626321775495' |
| 2 |
Halted |
0 ms |
0 KB |
- |
