#include "fish.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
const int MAXN = 100100;
typedef long long ll;
typedef pair<int, int> pi;
vector<pi> c[MAXN];
vector<int> fish[MAXN];
vector<ll> sum[MAXN], dp[MAXN][3], a[4];
void f(int i, int N) {
int it2;
if(i+1 < N) {
if(fish[i].size()) {
it2 = upper_bound(c[i+1].begin(), c[i+1].end(), pi(fish[i][(int)fish[i].size()-1], INT_MAX)) - c[i+1].begin();
a[0].push_back(dp[i][2][(int)fish[i].size()-1] + sum[i+1][it2]);
}
for(int j = (int)fish[i].size()-2; j >= 0; j--) {
it2 = upper_bound(c[i+1].begin(), c[i+1].end(), pi(fish[i][j], INT_MAX)) - c[i+1].begin();
a[0].push_back(max(*a[0].rbegin(), dp[i][2][j] + sum[i+1][it2]));
}
reverse(a[0].begin(), a[0].end());
}
if(fish[i].size()) {
it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i][0], INT_MAX)) - c[i].begin();
a[1].push_back(dp[i][0][0] - sum[i][it2]);
}
for(int j = 1; j < fish[i].size(); j++) {
it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i][j], INT_MAX)) - c[i].begin();
a[1].push_back(max(*a[1].rbegin(), dp[i][0][j] - sum[i][it2]));
}
if(i) {
if(fish[i-1].size()) {
a[2].push_back(dp[i-1][2][0]);
}
for(int j = 1; j < fish[i-1].size(); j++) {
a[2].push_back(max(*a[2].rbegin(), dp[i-1][2][j]));
}
if(fish[i-1].size()) {
it2 = upper_bound(c[i].begin(), c[i].end(), pi(*fish[i].rbegin(), INT_MAX)) - c[i].begin();
a[3].push_back(dp[i-1][2][(int)fish[i-1].size()-1] + sum[i][it2]);
}
for(int j = (int)fish[i-1].size()-2; j >= 0; j--) {
it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i][j], INT_MAX)) - c[i].begin();
a[3].push_back(max(*a[2].rbegin(), dp[i][0][j] + sum[i][it2]));
}
reverse(a[3].begin(), a[3].end());
}
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
for(int i = 0; i < M; i++) {
c[X[i]].push_back(pi(Y[i]+1, W[i]));
}
for(int i = 0; i < N; i++) sort(c[i].begin(), c[i].end());
for(int i = 0; i < N; i++) {
fish[i].push_back(0);
if(i) for(pi j : c[i-1]) fish[i].push_back(j.first);
if(i+1 < N) for(pi j : c[i+1]) fish[i].push_back(j.first);
sort(fish[i].begin(), fish[i].end());
fish[i].erase(unique(fish[i].begin(), fish[i].end()), fish[i].end());
}
for(int i = 0; i < N; i++) {
sum[i].push_back(0);
for(pi t : c[i]) sum[i].push_back(*sum[i].rbegin()+t.second);
}
// for(int i = 0; i < N; i++)
// for(pi t : c[i]) cout<<t.first<<" "<<t.second<<" ";
// cout<<endl;
// for(int i = 0; i < N; i++) {
// for(int t : fish[i]) cout<<t<<" ";
// cout<<endl;
// }
// cout<<endl;
// for(int i = 0; i < N; i++) {
// for(int t : sum[i]) cout<<t<<" ";
// cout<<endl;
// }
// cout<<endl;
// for(int j = 0; j <= N; j++) {
// for(int k = j; k <= N; k++) {
// dp[2][j][1] = max(dp[2][j][1], sum[2][k] - sum[2][j]);
// }
// for(int k = 0; k < j; k++) {
// dp[2][j][0] = max(dp[2][j][0], sum[1][j] - sum[1][k]);
// }
//
// dp[2][j][2] = max(dp[2][j][0], dp[2][j][1]);
// }
// for(int j = 0; j <= N; j++) {
// update(1, 0, N, j, dp[2][j][2] + sum[3][j], 0);
// update(1, 0, N, j, dp[2][j][0] - sum[2][j], 1);
// update(1, 0, N, j, dp[1][j][2], 2);
// update(1, 0, N, j, dp[1][j][2] + sum[2][j], 3);
// }
// a[0][1] = LLONG_MIN;
// a[0][2] = dp[1][0][2];
// for(int j = 1; j <= N; j++) {
// a[j][1] = max(a[j-1][1], dp[2][j][0] - sum[2][j]);
// a[j][2] = max(a[j-1][2], dp[1][j][2]);
// }
//
// a[N][0] = dp[2][N][2] + sum[3][N];
// a[N][3] = dp[1][N][2] + sum[2][N];
// for(int j = N-1; j >= 0; j--) {
// a[j][0] = max(a[j+1][0], dp[2][j][2] + sum[3][j]);
// a[j][3] = max(a[j+1][3], dp[1][j][2] + sum[2][j]);
// }
for(int t : fish[0]) for(int j = 0; j < 3; j++) dp[0][j].push_back(0);
f(0, N);
int it1, it2;
for(int i = 1; i < N; i++) {
for(int k = 0; k < 3; k++) dp[i][k].resize(fish[i].size());
for(int j = 0; j < fish[i].size(); j++) {
// for(int k = j; k <= N; k++) {
// //dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][2] + sum[i][k] - sum[i][j]);
//
// //if(i==N&&j==N-1)cout<<dp[i][j]<<" ";
// }
//dp[i][j][1] = solve(1, 0, N, j, N, 0) - sum[i][j];
int v = fish[i][j];
it1 = lower_bound(fish[i-1].begin(), fish[i-1].end(), v) - fish[i-1].begin();
it2 = upper_bound(c[i].begin(), c[i].end(), pi(v, INT_MAX)) - c[i].begin();
if(it1 < fish[i-1].size()) dp[i][1][j] = a[0][it1] - sum[i][it2];
//cout<<endl;
// for(int k = 1; k < j; k++) {
// dp[i][j][0] = max(dp[i][j][0], dp[i-1][k][0] + sum[i-1][j] - sum[i-1][k]);
//
// if(i==N&&j==N-1) cout<<dp[i][j]<<" ";
// }
//dp[i][j][0] = solve(1, 0, N, 1, j-1, 1) + sum[i-1][j];
dp[i][0][j] = LLONG_MIN;
//it1 = upper_bound(fish[i-1].begin(), fish[i-1].end(), j) - fish[i-1].begin();
it2 = upper_bound(c[i-1].begin(), c[i-1].end(), pi(v, INT_MAX)) - c[i-1].begin();
if(it1) dp[i][0][j] = a[1][it1-1] + sum[i-1][it2];
//cout<<endl;
//for(int k = 0; k <= N; k++) {
//dp[i][j][0] = max(dp[i][j][0], dp[i-2][k][2] + sum[i-1][max(k, j)]);
//if(i==N&&j==N-1) cout<<dp[i][j]<<" ";
//}
//dp[i][j][0] = max(dp[i][j][0], solve(1, 0, N, 0, j, 2) + sum[i-1][j]);
if(i > 1) {
it1 = upper_bound(fish[i-2].begin(), fish[i-2].end(), v) - fish[i-2].begin();
if(it1) dp[i][0][j] = max(dp[i][0][j], a[2][it1-1] + sum[i-1][it2]);
//dp[i][j][0] = max(dp[i][j][0], solve(1, 0, N, j+1, N, 3));
//it1 = lower_bound(fish[i-2].begin(), fish[i-2].end(), j) - fish[i-2].begin();
if(it1 < fish[i-2].size()) dp[i][0][j] = max(dp[i][0][j], a[3][it1]);
}
dp[i][2][j] = max(dp[i][0][j], dp[i][1][j]);
// cout<<i<<" "<<j<<endl;
// for(int t = 0; t<3;t++)cout<<dp[i][t][j]<<" ";
// cout<<endl;
}
for(int k = 0; k < 4; k++) a[k].clear();
f(i, N);
// a[0][0] = dp[i][0][2] + sum[i+1][0];
// a[0][1] = LLONG_MIN;
// a[0][2] = dp[i-1][0][2];
// a[0][3] = dp[i-1][0][2] + sum[i][0];
// for(int j = 1; j <= N; j++) {
// a[j][0] = max(a[j-1][0], dp[i][j][2] + sum[i+1][j]);
// a[j][1] = max(a[j-1][1], dp[i][j][0] - sum[i][j]);
// a[j][2] = max(a[j-1][2], dp[i-1][j][2]);
// a[j][3] = max(a[j-1][3], dp[i-1][j][2] + sum[i][j]);
// }
//
// b[N][0] = dp[i][N][2] + sum[i+1][N];
// b[N][1] = dp[i][N][0] - sum[i][N];
// b[N][2] = dp[i-1][N][2];
// b[N][3] = dp[i-1][N][2] + sum[i][N];
// for(int j = N-1; j >= 0; j--) {
// b[j][0] = max(b[j+1][0], dp[i][j][2] + sum[i+1][j]);
// b[j][1] = max(b[j+1][1], dp[i][j][0] - sum[i][j]);
// b[j][2] = max(b[j+1][2], dp[i-1][j][2]);
// b[j][3] = max(b[j+1][3], dp[i-1][j][2] + sum[i][j]);
// }
}
// for(int i = 1; i <= N; i++) {
// for(int j =0; j <= N; j++) cout<<dp[i][j]<<" ";
// cout<<endl;
// }
long long ans = 0;
for(int j = 0; j < fish[N-1].size(); j++) ans = max(ans, dp[N-1][2][j]);
return ans;
}
Compilation message
fish.cpp: In function 'void f(int, int)':
fish.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j = 1; j < fish[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
fish.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int j = 1; j < fish[i-1].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:127:13: warning: unused variable 't' [-Wunused-variable]
127 | for(int t : fish[0]) for(int j = 0; j < 3; j++) dp[0][j].push_back(0);
| ^
fish.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int j = 0; j < fish[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
fish.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | if(it1 < fish[i-1].size()) dp[i][1][j] = a[0][it1] - sum[i][it2];
| ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:169:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | if(it1 < fish[i-2].size()) dp[i][0][j] = max(dp[i][0][j], a[3][it1]);
| ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:211:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for(int j = 0; j < fish[N-1].size(); j++) ans = max(ans, dp[N-1][2][j]);
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
55364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14292 KB |
Output is correct |
| 2 |
Runtime error |
167 ms |
72288 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
30036 KB |
Output is correct |
| 2 |
Correct |
41 ms |
29948 KB |
Output is correct |
| 3 |
Correct |
85 ms |
31436 KB |
Output is correct |
| 4 |
Correct |
73 ms |
31996 KB |
Output is correct |
| 5 |
Correct |
97 ms |
35472 KB |
Output is correct |
| 6 |
Correct |
94 ms |
35536 KB |
Output is correct |
| 7 |
Correct |
114 ms |
35408 KB |
Output is correct |
| 8 |
Correct |
107 ms |
35412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14308 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14292 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 8 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 9 |
Incorrect |
11 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '222459433080' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14308 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14292 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 8 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 9 |
Incorrect |
11 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '222459433080' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14308 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14292 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 8 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 9 |
Incorrect |
11 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '222459433080' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
30036 KB |
Output is correct |
| 2 |
Correct |
41 ms |
29948 KB |
Output is correct |
| 3 |
Correct |
85 ms |
31436 KB |
Output is correct |
| 4 |
Correct |
73 ms |
31996 KB |
Output is correct |
| 5 |
Correct |
97 ms |
35472 KB |
Output is correct |
| 6 |
Correct |
94 ms |
35536 KB |
Output is correct |
| 7 |
Correct |
114 ms |
35408 KB |
Output is correct |
| 8 |
Correct |
107 ms |
35412 KB |
Output is correct |
| 9 |
Correct |
122 ms |
35452 KB |
Output is correct |
| 10 |
Incorrect |
114 ms |
27588 KB |
1st lines differ - on the 1st token, expected: '36454348383152', found: '37477027973107' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
55364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
