//#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define imx INT_MAX
const long long MMX = (long long)(1e18);
typedef long long LL;
vector<pair<int,LL> > dw[100005],val[100005];
vector<pair<int,pair<int,int> > >up[100005];
vector<pair<LL,int> >lup[100005],ldw[100005],lze[100005];
vector<LL>rup[100005];
int c1,c2,si1,si2,c3,cr,crr;
LL ze[100005],rr,rrdw,rrup;
long long max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
for(int i=0;i<M;i++){
up[X[i]+2].pb({Y[i]+1,{W[i],-1}});
up[X[i]].pb({Y[i]+1,{W[i],1}});
dw[X[i]].pb({Y[i]+1,W[i]});
val[X[i]+1].pb({Y[i]+1,W[i]});
}
for(int i=1;i<=N;i++){
sort(all(up[i]));
sort(all(dw[i]));
sort(all(val[i]));
}
lze[0].pb({0,0});
for(int i=1;i<=N;i++){
for(int j=0;j<dw[i].size();j++){
ldw[i].pb({0,dw[i][j].F});
if(j!=0)dw[i][j].S+=dw[i][j-1].S;
}
c1=lup[i-1].size()-1,c2=ldw[i-1].size()-1,c3=val[i].size()-1,rr=-1;
rrdw=0;
for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
for(int j=ldw[i].size()-1;j>-1;j--){
cr=ldw[i][j].S;
if(c1!=-1){
while(lup[i-1][c1].S>=cr){
rr=max(rr,lup[i-1][c1].F);
c1--;
if(c1==-1)break;
}
}
if(c2!=-1){
while(ldw[i-1][c2].S>=cr){
rr=max(rr,ldw[i-1][c2].F);
c2--;
if(c2==-1)break;
}
}
if(c3!=-1){
while(val[i][c3].F>cr){
rrdw-=val[i][c3].S;
c3--;
if(c3==-1)break;
}
}
if(rr==-1)continue;
ldw[i][j].F=rr+dw[i][j].S-rrdw;
}
c1=0,c2=0,c3=0,rrup=0,rrdw=0,rr=-MMX;
for(int j=0;j<up[i].size();j++){
rrup+=up[i][j].S.F;
if(j!=up[i].size()-1){
if(up[i][j].F==up[i][j+1].F)continue;
}
cr=up[i][j].F;
if(c1!=lup[i-1].size()){
while(lup[i-1][c1].S<=cr){
crr=lup[i-1][c1].S;
if(c2!=val[i-1].size()){
while(val[i-1][c2].F<=crr){
rrdw-=val[i-1][c2].S;
c2++;
if(c2==val[i-1].size())break;
}
}
if(c3!=val[i].size()){
while(val[i][c3].F<=crr){
rrdw-=val[i][c3].S;
c3++;
if(c3==val[i].size())break;
}
}
//printf("// %lld",rrdw);
rr=max(rr,lup[i-1][c1].F+rrdw);
c1++;
if(c1==lup[i-1].size())break;
}
}
rup[i].pb(rrup);
if(rr==-MMX){
lup[i].pb({0,up[i][j].F});
continue;
}
//printf("=/ %lld %lld",rrup,rr);
lup[i].pb({rrup+rr,up[i][j].F});
}
c1=lze[i-1].size()-1,c2=val[i-1].size()-1,rrdw=0,rr=-1;
for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
for(int j=lup[i].size()-1;j>-1;j--){
cr=lup[i][j].S;
if(c1!=-1){
while(lze[i-1][c1].S>=cr){
rr=max(rr,lze[i-1][c1].F);
c1--;
if(c1==-1)break;
}
}
if(c2!=-1){
while(val[i-1][c2].F>cr){
rrdw+=val[i-1][c2].S;
c2--;
if(c2==-1)break;
}
}
if(rr==-1)continue;
//printf("//%d %lld\n",lup[i][j].S,rr+rup[i][j]+rrdw);
lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]+rrdw);
}
c1=0,c2=0,rr=-1,rrdw=0;
for(int j=0;j<lup[i].size();j++){
cr=lup[i][j].S;
if(c1!=lze[i-1].size()){
while(lze[i-1][c1].S<=cr){
crr=lze[i-1][c1].S;
if(c2!=val[i-1].size()){
while(val[i-1][c2].F<=crr){
rrdw-=val[i-1][c2].S;
c2++;
if(c2==val[i-1].size())break;
}
}
rr=max(rr,lze[i-1][c1].F+rrdw);
c1++;
if(c1==lze[i-1].size())break;
}
}
if(rr==-1)continue;
lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]);
}
lze[i].pb({ze[i-1],0});
si1=lup[i-1].size();
si2=ldw[i-1].size();
lup[i-1].pb({0,imx});
ldw[i-1].pb({0,imx});
for(c1=0,c2=0;c1<si1||c2<si2;){
ze[i]=max(ze[i],lup[i-1][c1].F);
ze[i]=max(ze[i],ldw[i-1][c2].F);
if(lup[i-1][c1].S<ldw[i-1][c2].S){
lze[i].pb(lup[i-1][c1]);
c1++;
}
else if(lup[i-1][c1].S>ldw[i-1][c2].S){
lze[i].pb(ldw[i-1][c2]);
c2++;
}
else{
lze[i].pb({max(lup[i-1][c1].F,ldw[i-1][c2].F),lup[i-1][c1].S});
c1++,c2++;
}
}
//printf("=%d=\n",i);
// for(int j=0;j<lup[i].size();j++)printf("%lld %d\n",lup[i][j].F,lup[i][j].S);
// for(int j=0;j<ldw[i].size();j++)printf("[%lld %d]\n",ldw[i][j].F,ldw[i][j].S);
// for(int j=0;j<lze[i].size();j++)printf("{%lld %d}\n",lze[i][j].F,lze[i][j].S);
}
LL ans=0;
for(int i=0;i<lze[N].size();i++)ans=max(ans,lze[N][i].F);
for(int i=0;i<lup[N].size();i++)ans=max(ans,lup[N][i].F);
for(int i=0;i<ldw[N].size();i++)ans=max(ans,ldw[N][i].F);
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:32:18: 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]
32 | for(int j=0;j<dw[i].size();j++){
| ~^~~~~~~~~~~~~
fish.cpp:39:18: 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]
39 | for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
| ~^~~~~~~~~~~~~~
fish.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int j=0;j<up[i].size();j++){
| ~^~~~~~~~~~~~~
fish.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(j!=up[i].size()-1){
| ~^~~~~~~~~~~~~~~~
fish.cpp:74:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if(c1!=lup[i-1].size()){
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:77:16: 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]
77 | if(c2!=val[i-1].size()){
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:81:20: 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]
81 | if(c2==val[i-1].size())break;
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:84:16: 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]
84 | if(c3!=val[i].size()){
| ~~^~~~~~~~~~~~~~~
fish.cpp:88:20: 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]
88 | if(c3==val[i].size())break;
| ~~^~~~~~~~~~~~~~~
fish.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(c1==lup[i-1].size())break;
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:107:18: 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]
107 | for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
| ~^~~~~~~~~~~~~~~~
fish.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int j=0;j<lup[i].size();j++){
| ~^~~~~~~~~~~~~~
fish.cpp:132:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | if(c1!=lze[i-1].size()){
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:135:16: 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]
135 | if(c2!=val[i-1].size()){
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:139:20: 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]
139 | if(c2==val[i-1].size())break;
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:144:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | if(c1==lze[i-1].size())break;
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:177:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int i=0;i<lze[N].size();i++)ans=max(ans,lze[N][i].F);
| ~^~~~~~~~~~~~~~
fish.cpp:178:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int i=0;i<lup[N].size();i++)ans=max(ans,lup[N][i].F);
| ~^~~~~~~~~~~~~~
fish.cpp:179:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for(int i=0;i<ldw[N].size();i++)ans=max(ans,ldw[N][i].F);
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
34592 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Incorrect |
132 ms |
49024 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
26068 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 |
10 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16668 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16664 KB |
Output is correct |
| 4 |
Correct |
10 ms |
16740 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 6 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 7 |
Correct |
11 ms |
16724 KB |
Output is correct |
| 8 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 9 |
Correct |
10 ms |
16872 KB |
Output is correct |
| 10 |
Correct |
11 ms |
17108 KB |
Output is correct |
| 11 |
Correct |
10 ms |
16832 KB |
Output is correct |
| 12 |
Correct |
10 ms |
16980 KB |
Output is correct |
| 13 |
Correct |
10 ms |
16788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
16900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16668 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16664 KB |
Output is correct |
| 4 |
Correct |
10 ms |
16740 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 6 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 7 |
Correct |
11 ms |
16724 KB |
Output is correct |
| 8 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 9 |
Correct |
10 ms |
16872 KB |
Output is correct |
| 10 |
Correct |
11 ms |
17108 KB |
Output is correct |
| 11 |
Correct |
10 ms |
16832 KB |
Output is correct |
| 12 |
Correct |
10 ms |
16980 KB |
Output is correct |
| 13 |
Correct |
10 ms |
16788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
16900 KB |
Output is correct |
| 15 |
Correct |
11 ms |
16724 KB |
Output is correct |
| 16 |
Incorrect |
10 ms |
17108 KB |
1st lines differ - on the 1st token, expected: '741526820812', found: '131260577826' |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16668 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16664 KB |
Output is correct |
| 4 |
Correct |
10 ms |
16740 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 6 |
Correct |
10 ms |
16724 KB |
Output is correct |
| 7 |
Correct |
11 ms |
16724 KB |
Output is correct |
| 8 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 9 |
Correct |
10 ms |
16872 KB |
Output is correct |
| 10 |
Correct |
11 ms |
17108 KB |
Output is correct |
| 11 |
Correct |
10 ms |
16832 KB |
Output is correct |
| 12 |
Correct |
10 ms |
16980 KB |
Output is correct |
| 13 |
Correct |
10 ms |
16788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
16900 KB |
Output is correct |
| 15 |
Correct |
11 ms |
16724 KB |
Output is correct |
| 16 |
Incorrect |
10 ms |
17108 KB |
1st lines differ - on the 1st token, expected: '741526820812', found: '131260577826' |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
26068 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 |
68 ms |
34592 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
