#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+1,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({0,0});
tmpbigger.push_back({0,0});
smaller.push_back({0,0});
smaller2.push_back({0,0});
bigger.push_back({0,0});
bigger2.push_back({0,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 = 0;j<sz;j++){
nwsmaller[j].first = v[i][j].first-1;
nwsmaller2[j].first = v[i][j].first-1;
nwbigger[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];
}
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 |
Incorrect |
69 ms |
30896 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
100 ms |
41612 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604093365756' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
11248 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
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 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 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 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 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 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
11248 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
30896 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569' |
| 2 |
Halted |
0 ms |
0 KB |
- |
