# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
859999 |
2023-10-11T10:45:28 Z |
jk410 |
Salesman (IOI09_salesman) |
C++17 |
|
609 ms |
30548 KB |
#include <iostream>
#include <algorithm>
#define maxx(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
struct market{
int t,l,m;
void input(){
cin>>t>>l>>m;
}
};
const ll INF=(int)1e18;
const int MAX=500001;
ll update(ll *tree,int x,ll v,int l,int r,int n){
if (r<x||x<l)
return tree[n];
if (l==r)
return maxx(tree[n],v);
int m=(l+r)>>1;
return tree[n]=max(update(tree,x,v,l,m,n<<1),update(tree,x,v,m+1,r,n<<1|1));
}
ll query(ll *tree,int lx,int rx,int l,int r,int n){
if (r<lx||rx<l)
return -INF;
if (lx<=l&&r<=rx)
return tree[n];
int m=(l+r)>>1;
return max(query(tree,lx,rx,l,m,n<<1),query(tree,lx,rx,m+1,r,n<<1|1));
}
int N,U,D,S;
market A[500001];
ll TreeU[1<<20],TreeD[1<<20];
ll DPU[500001],DPD[500001];
ll queryU(int idx){
ll umx=query(TreeU,A[idx].l,MAX,1,MAX,1);
if (umx==-INF)
return -INF;
return umx+A[idx].m+(ll)U*A[idx].l;
}
ll queryD(int idx){
ll dmx=query(TreeD,1,A[idx].l,1,MAX,1);
if (dmx==-INF)
return -INF;
return dmx+A[idx].m-(ll)D*A[idx].l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fill(TreeU+1,TreeU+(1<<20),-INF);
fill(TreeD+1,TreeD+(1<<20),-INF);
cin>>N>>U>>D>>S;
for (int i=0; i<N; i++)
A[i].input();
A[N]={MAX,S,0};
sort(A,A+N+1,[&](market a,market b)->bool{
if (a.t!=b.t)
return a.t<b.t;
return a.l<b.l;
});
update(TreeU,S,-(ll)U*S,1,MAX,1);
update(TreeD,S,(ll)D*S,1,MAX,1);
for (int r=0,l=0; r<=N; r++){
if (r==N||A[r+1].t!=A[r].t){
for (int i=l; i<=r; i++)
DPU[i]=DPD[i]=max(queryU(i),queryD(i));
for (int i=r-1; i>=l; i--)
maxx(DPU[i],DPU[i+1]+A[i].m-(ll)U*(A[i+1].l-A[i].l));
for (int i=l+1; i<=r; i++)
maxx(DPD[i],DPD[i-1]+A[i].m-(ll)D*(A[i].l-A[i-1].l));
for (int i=l; i<=r; i++){
update(TreeD,A[i].l,max(DPU[i],DPD[i])+(ll)D*A[i].l,1,MAX,1);
update(TreeU,A[i].l,max(DPU[i],DPD[i])-(ll)U*A[i].l,1,MAX,1);
}
l=r+1;
}
}
/*
for (int i=0; i<=N; i++){
DP[i]=-INF;
ll umx=query(TreeU,A[i].l,MAX,1,MAX,1);
if (umx!=-INF)
maxx(DP[i],umx+A[i].m+(ll)U*A[i].l);
ll dmx=query(TreeD,1,A[i].l,1,MAX,1);
if (dmx!=-INF)
maxx(DP[i],dmx+A[i].m-(ll)D*A[i].l);
update(TreeU,A[i].l,DP[i]-(ll)U*A[i].l,1,MAX,1);
update(TreeD,A[i].l,DP[i]+(ll)D*A[i].l,1,MAX,1);
}
cout<<DP[N];
*/
cout<<max(DPU[N],DPD[N]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
20824 KB |
Output is correct |
2 |
Correct |
3 ms |
20980 KB |
Output is correct |
3 |
Correct |
5 ms |
20828 KB |
Output is correct |
4 |
Correct |
7 ms |
20824 KB |
Output is correct |
5 |
Correct |
9 ms |
21000 KB |
Output is correct |
6 |
Correct |
33 ms |
21084 KB |
Output is correct |
7 |
Correct |
77 ms |
27288 KB |
Output is correct |
8 |
Correct |
119 ms |
27292 KB |
Output is correct |
9 |
Correct |
190 ms |
27104 KB |
Output is correct |
10 |
Correct |
348 ms |
29344 KB |
Output is correct |
11 |
Correct |
366 ms |
29344 KB |
Output is correct |
12 |
Correct |
471 ms |
29252 KB |
Output is correct |
13 |
Correct |
545 ms |
29376 KB |
Output is correct |
14 |
Correct |
582 ms |
30548 KB |
Output is correct |
15 |
Correct |
523 ms |
30548 KB |
Output is correct |
16 |
Correct |
609 ms |
30452 KB |
Output is correct |
17 |
Correct |
3 ms |
20828 KB |
Output is correct |
18 |
Correct |
3 ms |
20976 KB |
Output is correct |
19 |
Correct |
5 ms |
20828 KB |
Output is correct |
20 |
Correct |
7 ms |
20828 KB |
Output is correct |
21 |
Correct |
5 ms |
20828 KB |
Output is correct |
22 |
Correct |
7 ms |
20984 KB |
Output is correct |
23 |
Correct |
7 ms |
20828 KB |
Output is correct |
24 |
Correct |
7 ms |
20828 KB |
Output is correct |
25 |
Correct |
107 ms |
27116 KB |
Output is correct |
26 |
Correct |
215 ms |
27292 KB |
Output is correct |
27 |
Correct |
351 ms |
29344 KB |
Output is correct |
28 |
Correct |
406 ms |
29344 KB |
Output is correct |
29 |
Correct |
566 ms |
30544 KB |
Output is correct |
30 |
Correct |
538 ms |
30416 KB |
Output is correct |