| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 131881 | dragonslayerit | Salesman (IOI09_salesman) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
const long long INF=1e18+7;
int ts[500005];
int ls[500005];
int ms[500005];
long long dp[500005];
struct Event{
int x,p;
long long dp;
Event(int x,int p):x(x),p(p),dp(-INF){
}
bool operator<(const Event& e)const{
return x<e.x;
}
};
std::vector<Event> events[500005];
int N;
struct MaxSegTree{
static const int SIZE=500005;
long long st[SIZE*2];
MaxSegTree(){
std::fill(st,st+SIZE*2,-INF);
}
void pull(int i){
st[i]=std::max(st[i<<1],st[i<<1|1]);
}
void set(int i,long long v){
for(st[i+=SIZE]=v;i>1;i>>=1){
pull(i>>1);
}
}
long long query(int a,int b){
long long res=-INF;
for(a+=SIZE,b+=SIZE;a<b;a>>=1,b>>=1){
if(a&1) res=std::max(res,st[a++]);
if(b&1) res=std::max(res,st[--b]);
}
return res;
}
}up,down;
int main(){
int U,D,S;
scanf("%d %d %d %d",&N,&U,&D,&S);
S--;
for(int i=0;i<N;i++){
int T,L,M;
scanf("%d %d %d",&T,&L,&M);
events[T].emplace_back(L-1,M);
}
down.set(S,S*D);
up.set(S,-S*U);
for(int t=1;t<=500000;t++){
std::sort(events[t].begin(),events[t].end());
for(Event& e:events[t]){
long long v=e.p+std::max(down.query(0,e.x)-e.x*D,up.query(e.x,MaxSegTree::SIZE)+e.x*U);
down.set(e.x,v+e.x*D);
up.set(e.x,v-e.x*U);
e.dp=std::max(e.dp,v);
}
for(int e:events[t]){
down.set(e.x,-INF);
up.set(e.x,-INF);
}
std::reverse(events[t].begin(),events[t].end());
for(Event& e:events[t]){
long long v=e.p+std::max(down.query(0,e.x)-e.x*D,up.query(e.x,MaxSegTree::SIZE)+e.x*U);
down.set(e.x,v+e.x*D);
up.set(e.x,v-e.x*U);
e.dp=std::max(e.dp,v);
}
for(int e:events[t]){
down.set(e.x,e.dp+e.x*D);
up.set(e.x,e.dp-e.x*U);
}
}
printf("%lld\n",std::max(down.query(0,S)-S*D,up.query(S,MaxSegTree::SIZE)+S*U));
return 0;
}