#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define S second
#define F first
long long max_weights(int n,int m,vector<int> X,vector<int> Y,vector<int> W) {
vector<vll> v (n+5,vll {-1}), w(n+5,vll {0});
vector<vpll> la (n+5,vpll {{-1,0}});
ll r=0;
for(int i=0;i<m;i++){
if(X[i]>0)la[X[i]].push_back({Y[i],0});
la[X[i]+1].push_back({Y[i],W[i]});
la[X[i]+1].push_back({Y[i]-1,0});
la[X[i]+2].push_back({Y[i],0});
}
for(int i=0;i<=n;i++){
sort(la[i].begin(),la[i].end());
// cerr<<i<<"{\n";
for(int j=1;j<la[i].size();j++){
if(la[i][j].F==la[i][j-1].F)continue;
v[i].push_back(la[i][j].F);
w[i].push_back(la[i][j].S);
w[i][j]+=w[i][j-1];
//cerr<<v[i].back()<<"->"<<w[i].back()<<"\n";
}
// cerr<<"}\n";
}
vll t1{{}},t2{{}},t3{{}},t4{{}};
vll h2[2]={{},{}},h1[2]={{0},{0}};
for(int i=1;i<=n;i++){
t1=h1[0];
for(int j=0;j<h1[0].size();j++){
t1[j]=t1[j]-w[i-1][j];
// cerr<<t1[j]<<" ";
if(j>0)t1[j]=max(t1[j],t1[j-1]);
}//cerr<<"..................\n";
t2=h2[1];
for(int j=0;j<h2[0].size();j++){
// cerr<<t2[j]<<" ";
if(j>0)t2[j]=max(t2[j],t2[j-1]);
}//cerr<<"..................\n";
t3=h2[1];ll p=v[i-1].size()-1;
for(int j=h2[0].size()-1;j>=0;j--){
while(p>=0 && v[i-1][p]>v[i-2][j])p--;
if(p>-1)t3[j]=t3[j]+w[i-1][j];
// cerr<<t3[j]<<" ";
if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]);
}//cerr<<"..................\n";
t4=h1[1];p=v[i].size()-1;
for(int j=h1[1].size()-1;j>=0;j--){
while(p>=0 && v[i][p]>v[i-1][j])p--;
//cerr<<v[i-1][j]<<">="<<v[i][p]<<" "<<w[i][p]<<":\n";
t4[j]=t4[j]+w[i][p];
// cerr<<t4[j]<<"\n";
if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]);
}//cerr<<"..................\n";
ll p1=-1,p2=-1;
vll h[2]={{},{}};
for(int j=0;j<v[i].size();j++){
ll dp[2]={0,0};
//cerr<<i<<" "<<j<<"->"<<v[i][j]<<":\n";
if(i>=2){
while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++;
while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++;
if(p1>-1) dp[0]=max(dp[0],t1[p1]+w[i-1][p1]);//dp[i-1][k][0]-co[i-1][k]+co[i-1][j]
// cerr<<dp[0]<<" "<<dp[1]<<"(:\n";
if(p2>-1) dp[0]=max(dp[0],t2[p2]+w[i-1][p1]);//dp[i-2][k][1] +co[i-1][j]
if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]); //dp[i-2][k][1]+co[i-1][k]
dp[1]=dp[0];
if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j]
}
// cerr<<dp[0]<<" "<<dp[1]<<"\n";
h[0].push_back(dp[0]);
h[1].push_back(dp[1]);
r=max(h[0].back(),max(r,h[1].back()));
}
h2[0]=h1[0];h1[0]=h[0];
h2[1]=h1[1];h1[1]=h[1];
}
return r;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int j=1;j<la[i].size();j++){
| ~^~~~~~~~~~~~~
fish.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int j=0;j<h1[0].size();j++){
| ~^~~~~~~~~~~~~
fish.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j=0;j<h2[0].size();j++){
| ~^~~~~~~~~~~~~
fish.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]);
| ~~~^~~~~~~~~~~~~
fish.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]);
| ~~~^~~~~~~~~~~~~
fish.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j=0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
fish.cpp:66:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++;
| ~~~~^~~~~~~~~~~~~~
fish.cpp:67:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++;
| ~~~~^~~~~~~~~~~~~~
fish.cpp:71:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]); //dp[i-2][k][1]+co[i-1][k]
| ~~^~~~~~~~~~~~~~~~
fish.cpp:73:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j]
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
47688 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
86 ms |
63220 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
28 ms |
16876 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
23888 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '509833355105' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
16728 KB |
Output is correct |
| 2 |
Correct |
28 ms |
16876 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
23888 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '509833355105' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
47688 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
