#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
vector<pair<int,int>> v[N];
vector<long long>pre[N];
for(int i = 0;i<M;i++){
v[X[i]].push_back({Y[i],W[i]});
}
for(int i = 0;i<N;i++){
v[i].push_back({N,0});
sort(v[i].begin(),v[i].end());
pre[i].assign(v[i].size(),0);
for(int j = 0;j<v[i].size();j++){
pre[i][j] = v[i][j].second + (j?pre[i][j-1]:0);
}
}
vector<pair<int,long long>> tmpsmaller;
vector<pair<int,long long>> tmpbigger;
vector<pair<int,long long>> smaller;
vector<pair<int,long long>> smaller2;
vector<pair<int,long long>> bigger;
vector<pair<int,long long>> bigger2;
tmpsmaller.push_back({-1,0});
tmpbigger.push_back({-1,0});
smaller.push_back({-1,0});
smaller2.push_back({-1,0});
bigger.push_back({-1,0});
bigger2.push_back({-1,0});
for(int i = 0;i<N;i++){
int sz = v[i].size();
int prevsz = smaller.size();
vector<pair<int,long long>> nwsmaller(sz,{0,-1e18});
vector<pair<int,long long>> nwsmaller2(sz,{0,-1e18});
vector<pair<int,long long>> nwtmpsmaller(sz,{0,-1e18});
vector<pair<int,long long>> nwbigger(sz,{0,-1e18});
vector<pair<int,long long>> nwbigger2(sz,{0,-1e18});
vector<pair<int,long long>> nwtmpbigger(sz,{0,-1e18});
vector<pair<int,long long>> smaller3;
vector<pair<int,long long>> smaller4;
vector<pair<int,long long>> bigger3;
vector<pair<int,long long>> bigger4;
int pt1 = -1;
for(int j = 0;j<prevsz;j++){
while(i && pt1 != sz && v[i][pt1+1].first <= v[i-1][j].first-1)
pt1++;
smaller3.push_back({tmpsmaller[j].first,tmpsmaller[j].second + (pt1 == -1?0:pre[i][pt1])});
smaller4.push_back({tmpsmaller[j].first,tmpsmaller[j].second});
bigger3.push_back({tmpbigger[j].first,tmpbigger[j].second + (pt1 == -1?0:pre[i][pt1])});
bigger4.push_back({tmpbigger[j].first,tmpbigger[j].second});
}
for(int j = prevsz-2;j>=0;j--){
smaller3[j] = max(smaller3[j],smaller3[j+1]);
smaller4[j] = max(smaller4[j],smaller4[j+1]);
bigger3[j] = max(bigger3[j],bigger3[j+1]);
bigger4[j] = max(bigger4[j],bigger4[j+1]);
}
for(int j = 0;j<sz;j++){
nwsmaller[j].first = v[i][j].first-1;
nwsmaller2[j].first = v[i][j].first-1;
nwtmpsmaller[j].first = v[i][j].first-1;
nwbigger[j].first = v[i][j].first-1;
nwbigger2[j].first = v[i][j].first-1;
nwtmpbigger[j].first = v[i][j].first-1;
}
pt1 = -1;
for(int j = 0;j<sz;j++){
while(pt1 != prevsz - 1 && smaller[pt1 + 1].first < v[i][j].first)
pt1++;
if(pt1 != -1){
nwbigger[j].second = max(nwbigger[j].second,smaller[pt1].second);
nwbigger[j].second = max(nwbigger[j].second,smaller2[pt1].second + (i?pre[i-1][pt1]:0));
nwbigger[j].second = max(nwbigger[j].second,bigger2[pt1].second + (i?pre[i-1][pt1]:0));
}
nwbigger2[j].second = nwbigger[j].second - (j?pre[i][j-1]:0);
nwtmpbigger[j] = nwbigger[j];
if(j){
nwbigger[j].second = max(nwbigger[j].second,nwbigger[j-1].second);
nwbigger2[j].second = max(nwbigger2[j].second,nwbigger2[j-1].second);
}
}
pt1 = 0;
for(int j = 0;j<sz;j++){
while(pt1 != prevsz && smaller[pt1].first < v[i][j].first)
pt1++;
if(pt1 != prevsz){
nwsmaller[j].second = max(nwsmaller[j].second,smaller3[pt1].second - (j?pre[i][j-1]:0));
nwsmaller[j].second = max(nwsmaller[j].second,bigger3[pt1].second - (j?pre[i][j-1]:0));
nwsmaller2[j].second = max(nwsmaller2[j].second,smaller4[pt1].second);
nwsmaller2[j].second = max(nwsmaller2[j].second,bigger4[pt1].second);
}
nwtmpsmaller[j] = nwsmaller[j];
if(j){
nwsmaller[j].second = max(nwsmaller[j].second,nwsmaller[j-1].second);
nwsmaller2[j].second = max(nwsmaller2[j].second,nwsmaller2[j-1].second);
}
}
smaller = nwsmaller;
smaller2 = nwsmaller2;
tmpsmaller = nwtmpsmaller;
bigger = nwbigger;
bigger2 = nwbigger2;
tmpbigger = nwtmpbigger;
// cout << i << endl;
// for(auto u:tmpsmaller){
// cout << u.first << ' ' << u.second << endl;
// }
// cout << endl;
// for(auto u:tmpbigger){
// cout << u.first << ' ' << u.second << endl;
// }
// cout << endl;
}
return max(smaller.back().second,bigger.back().second);
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int j = 0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
30828 KB |
Output is correct |
2 |
Correct |
78 ms |
37196 KB |
Output is correct |
3 |
Correct |
32 ms |
11256 KB |
Output is correct |
4 |
Correct |
36 ms |
11240 KB |
Output is correct |
5 |
Correct |
173 ms |
47216 KB |
Output is correct |
6 |
Correct |
154 ms |
28348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
100 ms |
41696 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
11240 KB |
Output is correct |
2 |
Correct |
31 ms |
11148 KB |
Output is correct |
3 |
Incorrect |
54 ms |
12356 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
11240 KB |
Output is correct |
2 |
Correct |
31 ms |
11148 KB |
Output is correct |
3 |
Incorrect |
54 ms |
12356 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
30828 KB |
Output is correct |
2 |
Correct |
78 ms |
37196 KB |
Output is correct |
3 |
Correct |
32 ms |
11256 KB |
Output is correct |
4 |
Correct |
36 ms |
11240 KB |
Output is correct |
5 |
Correct |
173 ms |
47216 KB |
Output is correct |
6 |
Correct |
154 ms |
28348 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
100 ms |
41696 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
9 |
Halted |
0 ms |
0 KB |
- |