#include "fish.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define inc inc1337
#define dec dec1337
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e5;
int n, m;
vector<pii > fish[1 + maxn];
vector<int> reach[1 + maxn];
int len[1 + maxn];
vector<int> inc[1 + maxn];
vector<int> dec[1 + maxn];
int sm[1 + maxn];
int bi[1 + maxn];
int other;
int solve() {
for(int i = 0; i <= n; i++) {
//if(fish[i].size() == 1) {
fish[i].pb(mp(n + 1, 0));
//}
len[i] = fish[i].size() - 1;
dec[i].resize(1 + len[i]);
inc[i].resize(1 + len[i]);
for(const pii &p : fish[i]) {
if(p.fi != 0) {
reach[i].pb(p.fi - 1);
}
}
reach[i].pb(n + 1);
}
for(int i = 1; i <= n; i++) {
// inc
{
vector<int> v(1 + len[i - 1]);
v[0] = inc[i - 1][0];
int pref = 0;
for(int j = 1; j <= len[i - 1]; j++) {
pref += fish[i - 1][j].se;
v[j] = inc[i - 1][j] - pref;
v[j] = max(v[j], v[j - 1]);
}
int k = 0;
pref = 0;
for(int j = 1; j <= len[i]; j++) {
while(k < len[i - 1] && fish[i - 1][k + 1].fi <= reach[i][j]) {
k++;
pref += fish[i - 1][k].se;
}
inc[i][j] = pref + v[k];
// itt az is benne van, ha az elozo
// reach-je a mostani fele log es esetleg
// valamit include-ol, de az nem szamit,
// mert nem adjuk hozza, es kulon esetben
// viszont lekezeljuk
}
}
// dec
{
vector<int> v(1 + len[i - 1]);
int pref = 0;
for(int j = 1; j <= len[i]; j++) {
pref += fish[i][j].se;
}
int k = len[i];
for(int j = len[i - 1]; j >= 1; j--) {
while(fish[i][k].fi > reach[i - 1][j]) {
pref -= fish[i][k].se;
k--;
}
v[j] = dec[i - 1][j] + pref;
if(j < len[i - 1]) {
v[j] = max(v[j], v[j + 1]);
}
}
v[0] = max(v[0], v[1]);
k = len[i - 1];
pref = 0;
for(int j = len[i]; j >= 1; j--) {
pref += fish[i][j].se;
}
for(int j = len[i]; j >= 0; j--) {
while(k > 0 && fish[i][j].fi <= reach[i - 1][k - 1]) {
k--;
}
dec[i][j] = v[k] - pref;
// itt is van hasonlo eset ami
// mashol kezelve van
pref -= fish[i][j].se;
}
}
// sm
if(i >= 2) {
vector<int> v(1 + len[i - 2]);
int pref = 0;
for(int j = 1; j <= len[i - 1]; j++) {
pref += fish[i - 1][j].se;
}
int k = len[i - 1];
for(int j = len[i - 2]; j >= 1; j--) {
while(fish[i - 1][k].fi > reach[i - 2][j]) {
pref -= fish[i - 1][k].se;
k--;
}
v[j] = dec[i - 2][j] + pref;
if(j < len[i - 2]) {
v[j] = max(v[j], v[j + 1]);
}
}
for(int j = 1; j <= len[i]; j++) {
inc[i][j] = max(inc[i][j], v[1]);
}
int maxi_prev = 0;
for(int j = 1; j <= len[i - 2]; j++) {
maxi_prev = max(maxi_prev, dec[i - 2][j]);
}
k = 0;
pref = 0;
for(int j = 1; j <= len[i]; j++) {
while(k < len[i - 1] && fish[i - 1][k + 1].fi <= reach[i][j]) {
k++;
pref += fish[i - 1][k].se;
}
inc[i][j] = max(inc[i][j], maxi_prev + pref);
}
}
// bi
bi[i] = inc[i][len[i]];
// other
dec[i][len[i]] = max(dec[i][len[i]], bi[i]);
}
// for(int i = 0; i <= n; i++) {
// cout << i << ":\n";
// cout << "fish" << "\n";
// for(pii p : fish[i]) {
// cout << p.fi << " " << p.se << "\n";
// }
// cout << "reach" << "\n";
// for(int x : reach[i]) {
// cout << x << " ";
// }
// cout << "\n";
// cout << "len" << "\n";
// cout << len[i] << "\n";
// cout << "inc" << "\n";
// for(int x : inc[i]) {
// cout << x << " ";
// }
// cout << "\n";
// cout << "dec" << "\n";
// for(int x : dec[i]) {
// cout << x << " ";
// }
// cout << "\n";
// cout << "sm bi" << "\n";
// cout << sm[i] << " " << bi[i] << "\n";
// // other
// }
int ans = 0;
for(int x : inc[n]) {
ans = max(ans, x);
}
for(int y : dec[n]) {
ans = max(ans, y);
}
ans = max(ans, sm[n]);
ans = max(ans, bi[n]);
return ans;
}
int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y, vector<signed> W) {
n = N, m = M;
for(int i = 0; i <= n; i++) {
fish[i].pb(mp(0, 0));
}
for(int i = 0; i < m; i++) {
fish[X[i] + 1].pb(mp(Y[i] + 1, W[i]));
}
for(int i = 1; i <= n; i++) {
sort(fish[i].begin(), fish[i].end());
}
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
30916 KB |
Output is correct |
| 2 |
Correct |
58 ms |
34248 KB |
Output is correct |
| 3 |
Correct |
28 ms |
25428 KB |
Output is correct |
| 4 |
Correct |
28 ms |
25436 KB |
Output is correct |
| 5 |
Correct |
119 ms |
51752 KB |
Output is correct |
| 6 |
Correct |
154 ms |
53792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9816 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 |
31 ms |
25424 KB |
Output is correct |
| 2 |
Correct |
29 ms |
25256 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
28500 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 |
4 ms |
9816 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 |
4 ms |
9816 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 |
4 ms |
9816 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 |
31 ms |
25424 KB |
Output is correct |
| 2 |
Correct |
29 ms |
25256 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
28500 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 |
55 ms |
30916 KB |
Output is correct |
| 2 |
Correct |
58 ms |
34248 KB |
Output is correct |
| 3 |
Correct |
28 ms |
25428 KB |
Output is correct |
| 4 |
Correct |
28 ms |
25436 KB |
Output is correct |
| 5 |
Correct |
119 ms |
51752 KB |
Output is correct |
| 6 |
Correct |
154 ms |
53792 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
9816 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
