# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
859993 | jk410 | Salesman (IOI09_salesman) | C++17 | 656 ms | 30804 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
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=r; i>=l; i--){
DPU[i]=-INF;
ll umx=query(TreeU,A[i].l,MAX,1,MAX,1);
if (umx!=-INF) {
DPU[i]=umx+A[i].m+(ll)U*A[i].l;
update(TreeU,A[i].l,DPU[i]-(ll)U*A[i].l,1,MAX,1);
}
}
for (int i=l; i<=r; i++){
DPD[i]=-INF;
ll dmx=query(TreeD,1,A[i].l,1,MAX,1);
if (dmx!=-INF){
DPD[i]=dmx+A[i].m-(ll)D*A[i].l;
update(TreeD,A[i].l,DPD[i]+(ll)D*A[i].l,1,MAX,1);
}
}
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 |
---|---|---|---|---|
Fetching results... |