#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 2e6 + 10,mni = -1e9 - 10;
// const int mxn = 310,mni = -1e9 - 10;
struct we
{
int dat,loc,mon;
};
bool cmp(const struct we &l,const struct we &r)
{
return l.loc < r.loc;
}
struct we sot[mxn] = {};
vector<int> eve[mxn] = {};
int val[mxn] = {},dco,uco,sel[mxn] = {},ser[mxn] = {},ale,ari,cval[mxn] = {}
,cvar[mxn] = {},fvap[mxn] = {},ans;
int fimi(int l,int r)
{
if(l < r)
{
return l;
}
return r;
}
int fima(int l,int r)
{
if(l > r)
{
return l;
}
return r;
}
int bui(int cl,int cr,int no)
{
sel[no] = mni;
ser[no] = mni;
if(cl == cr)
{
return 0;
}
int mid = (cl+cr) / 2;
bui(cl,mid,no*2);
bui(mid+1,cr,no*2+1);
return 0;
}
int ad(int cl,int cr,int no,int tar,int ava)
{
if(cl > tar || cr < tar)
{
return 0;
}
if(cl == cr)
{
sel[no] = ava;
ser[no] = ava;
return 0;
}
int mid = (cl+cr) / 2;
ad(cl,mid,no*2,tar,ava);
ad(mid+1,cr,no*2+1,tar,ava);
sel[no] = fima(sel[no*2],sel[no*2+1] - (mid+1 - cl) * uco);
ser[no] = fima(ser[no*2+1],ser[no*2] - (cr - mid) * dco);
return 0;
}
int fiva(int cl,int cr,int no,int tar)
{
if(cr < tar)
{
ale = fima(ale,ser[no] - (tar-cr) * dco);
return 0;
}
if(cl > tar)
{
ari = fima(ari,sel[no] - (cl - tar) * uco);
return 0;
}
if(cl == cr)
{
ale = fima(ale,val[cl]);
ari = fima(ari,val[cl]);
return 0;
}
int mid = (cl+cr) / 2;
fiva(cl,mid,no*2,tar);
fiva(mid+1,cr,no*2+1,tar);
return 0;
}
int main()
{
int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
ans = 0;
scanf("%d %d %d %d",&n,&uco,&dco,&spo);
for(i=0; i<n; i++)
{
scanf("%d %d %d",&sot[i].dat,&sot[i].loc,&sot[i].mon);
dma = fima(dma,sot[i].dat);
}
sot[n] = {0,spo,0};
sort(sot,sot + n+1,cmp);
m = sot[n].loc;
for(i=0; i<n+1; i++)
{
eve[sot[i].dat].push_back(i);
}
for(i=0; i<=m; i++)
{
val[i] = mni;
}
val[spo] = 0;
bui(0,m,1);
ad(0,m,1,spo,0);
for(i=1; i<=dma; i++)
{
if(eve[i].size() == 0)
{
continue;
}
for(j=0; j<eve[i].size(); j++)
{
cn = eve[i][j];
ale = mni;
ari = mni;
fiva(0,m,1,sot[cn].loc);
cval[j] = ale + sot[cn].mon;
cvar[j] = ari + sot[cn].mon;
fvap[j] = val[sot[cn].loc];
if(j != 0)
{
cval[j] = fima(cval[j],cval[j-1]
- (sot[cn].loc - sot[eve[i][j-1]].loc) * dco + sot[cn].mon);
}
}
for(j=eve[i].size()-2; j>=0; j--)
{
cn = eve[i][j];
{
cvar[j] = fima(cvar[j],cvar[j+1]
- (sot[eve[i][j+1]].loc - sot[cn].loc) * uco + sot[cn].mon);
}
}
for(j=0; j<eve[i].size(); j++)
{
cn = eve[i][j];
fvap[j] = fima(cval[j],fima(fvap[j],cvar[j]));
ad(0,m,1,sot[cn].loc,fvap[j]);
if(sot[cn].loc > spo)
{
cva = -uco * (sot[cn].loc - spo);
}
else
{
cva = -dco * (spo - sot[cn].loc);
}
ans = fima(ans,fvap[j] + cva);
val[sot[cn].loc] = fvap[j];
}
}
printf("%d\n",ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(j=0; j<eve[i].size(); j++)
| ~^~~~~~~~~~~~~~
salesman.cpp:145:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(j=0; j<eve[i].size(); j++)
| ~^~~~~~~~~~~~~~
salesman.cpp:94:36: warning: unused variable 'cm' [-Wunused-variable]
94 | int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
| ^~
salesman.cpp:94:39: warning: unused variable 'fn' [-Wunused-variable]
94 | int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
| ^~
salesman.cpp:94:42: warning: unused variable 'fm' [-Wunused-variable]
94 | int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
| ^~
salesman.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d %d %d %d",&n,&uco,&dco,&spo);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d %d %d",&sot[i].dat,&sot[i].loc,&sot[i].mon);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47312 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47300 KB |
Output is correct |
| 3 |
Correct |
30 ms |
47448 KB |
Output is correct |
| 4 |
Correct |
26 ms |
47472 KB |
Output is correct |
| 5 |
Correct |
28 ms |
47672 KB |
Output is correct |
| 6 |
Correct |
52 ms |
58696 KB |
Output is correct |
| 7 |
Correct |
92 ms |
60516 KB |
Output is correct |
| 8 |
Correct |
160 ms |
63464 KB |
Output is correct |
| 9 |
Correct |
208 ms |
65536 KB |
Output is correct |
| 10 |
Runtime error |
129 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
185 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
181 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
218 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
191 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
214 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Incorrect |
24 ms |
47316 KB |
Output isn't correct |
| 18 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
| 19 |
Incorrect |
25 ms |
47284 KB |
Output isn't correct |
| 20 |
Incorrect |
25 ms |
47444 KB |
Output isn't correct |
| 21 |
Incorrect |
26 ms |
47436 KB |
Output isn't correct |
| 22 |
Incorrect |
27 ms |
47632 KB |
Output isn't correct |
| 23 |
Incorrect |
27 ms |
47564 KB |
Output isn't correct |
| 24 |
Incorrect |
28 ms |
47556 KB |
Output isn't correct |
| 25 |
Incorrect |
100 ms |
60604 KB |
Output isn't correct |
| 26 |
Incorrect |
186 ms |
63972 KB |
Output isn't correct |
| 27 |
Incorrect |
318 ms |
65536 KB |
Output isn't correct |
| 28 |
Incorrect |
299 ms |
65536 KB |
Output isn't correct |
| 29 |
Runtime error |
178 ms |
65536 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
183 ms |
65536 KB |
Execution killed with signal 9 |
