#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)2e18 + 10;
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")
int cnt[NN];
vector<pair<int,long long>> val[NN];
vector<int> possibleLen[NN];
long long getSum(int x,int r){
if(val[x].empty())
return 0;
if(val[x][0].first >= r)
return 0;
return (upper_bound(val[x].begin(),val[x].end(),make_pair(r-1,INF))-1)->second;
}
mt19937 rnd(time(nullptr));
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
long long dp[2][333][333];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 333; j++){
for(int t = 0; t < 333; t++){
dp[i][j][t] = 0;
}
}
}
set<int> st[N+22];
for(int i = 0; i < M; i++){
// g[X[i]+2][Y[i]] = W[i];
val[X[i]+2].push_back(make_pair(Y[i],W[i]));
for(int j = max(2,X[i]+1); j <= X[i]+3; j++){
st[j].insert(Y[i]+1);
}
}
for(int i = 0; i < N+2; i++){
st[i].insert(0);
st[i].insert(N);
possibleLen[i] = vector<int>(st[i].begin(),st[i].end());
sort(val[i].begin(),val[i].end());
for(int j = 1; j < val[i].size(); j++){
val[i][j].second += val[i][j-1].second;
}
}
// cerr << getSum(2,3) << "\n";
// return 0;
long long ans = 0;
for(int i = 2; i < N+2; i++){
int pr[2];
for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
int lcur = possibleLen[i][cur];
int l1 = possibleLen[i-2][pr[1]];
pr[0] = lower_bound(possibleLen[i-1].begin(),possibleLen[i-1].end(),min(l1,lcur)-1) - possibleLen[i-1].begin();
pr[0] = max(0,pr[0]);
pr[0] = min((int)possibleLen[i-1].size()-1,pr[0]);
for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
int l0 = possibleLen[i-1][pr[0]];
if(lcur <= l0){
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,lcur));
} else if(lcur <= l1){
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0));
} else {
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0)
+ max(0ll,getSum(i-1,lcur)-getSum(i-1,l0)) - max(0ll,getSum(i-1,l1)-getSum(i-1,l0)));
}
ans = max(ans,dp[1][pr[0]][cur]);
// cerr << i << " " << l1 << " " << l0 << " " << lcur << " " << dp[1][pr[0]][cur] << "\n";
// if(dp[0][pr[0]][cur] == 0)
// continue;
}
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
dp[0][pr[1]][pr[0]] = 0;
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
dp[0][pr[0]][cur] = dp[1][pr[0]][cur];
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
dp[1][pr[0]][cur] = 0;
}
}
}
// for(int i = 0; i < N+2; i++){
// for(int j = 0; j < 10; j++){
// for(int t = 0; t < 10; t++){
// ans = max(ans,dp[i][j][t]);
// }
// }
// }
return ans;
}
/**
10000 2
0 0 1
0 1 1
5 4
0 2 5
1 1 2
4 4 1
3 3 3
**/
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:26: 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]
49 | for(int j = 1; j < val[i].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:62:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int cur = 0; cur < possibleLen[i].size(); cur++){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:85:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:86:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:90:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:91:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int cur = 0; cur < possibleLen[i].size(); cur++){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:95:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:96:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int cur = 0; cur < possibleLen[i].size(); cur++){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
67900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 2 |
Runtime error |
266 ms |
84400 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
35 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
82 ms |
27908 KB |
Output is correct |
| 4 |
Correct |
69 ms |
27980 KB |
Output is correct |
| 5 |
Correct |
183 ms |
34132 KB |
Output is correct |
| 6 |
Correct |
133 ms |
34224 KB |
Output is correct |
| 7 |
Correct |
138 ms |
34044 KB |
Output is correct |
| 8 |
Correct |
145 ms |
34092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
6740 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '215440286630' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
6740 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '215440286630' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6740 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
6740 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '215440286630' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
35 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
82 ms |
27908 KB |
Output is correct |
| 4 |
Correct |
69 ms |
27980 KB |
Output is correct |
| 5 |
Correct |
183 ms |
34132 KB |
Output is correct |
| 6 |
Correct |
133 ms |
34224 KB |
Output is correct |
| 7 |
Correct |
138 ms |
34044 KB |
Output is correct |
| 8 |
Correct |
145 ms |
34092 KB |
Output is correct |
| 9 |
Correct |
305 ms |
43620 KB |
Output is correct |
| 10 |
Incorrect |
157 ms |
24748 KB |
1st lines differ - on the 1st token, expected: '36454348383152', found: '36076396588953' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
67900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
