제출 #1254913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254913		mngoc._.	Salesman (IOI09_salesman)	C++20	60 / 100	581 ms	32460 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
const int INF = 1e18;
int dp[N];
int st[4 * N][2];
int n , u , d , s;
int mx;
struct Event{
	int t , l , m;
} event[N];

bool cmp(const Event& x , const Event& y){
    if(x.t != y.t) return x.t < y.t;
    if(x.m != y.m) return x.m < y.m;
    return x.l < y.l;
}

void build(int type , int idx , int l ,int r){
	if(l == r){
		st[idx][type] = -INF;
		return;
	}
	int mid = (l + r) / 2;
	build(type , 2 * idx , l , mid);
	build(type , 2 * idx + 1 , mid + 1 , r);
	st[idx][type] = max(st[2  * idx][type] , st[2 * idx + 1][type]);
}

int get(int type , int idx, int l , int r , int u , int v){
	if(l > v || r < u) return -INF;
	if(u <= l && r <= v) return st[idx][type];
	int mid = (l + r) / 2;
    return max(get(type , 2 * idx , l , mid , u , v) , get(type , 2 * idx + 1  , mid + 1 , r , u , v));
}

void update(int type , int idx , int l , int r , int pos , int v){
	if(l > pos || r < pos) return;
	if(l == r){
		st[idx][type] = max(st[idx][type] , v);
		return;
	}
	int mid = (l + r) / 2;
	update(type , 2 * idx , l , mid , pos , v);
	update(type , 2 * idx + 1 , mid + 1 , r , pos, v);
	st[idx][type] = max(st[2 * idx][type] , st[2 * idx + 1][type]);
}



void solve(void){
	cin >> n >> u >> d >> s;
	for(int i = 1 ; i <= n ; i++){
		cin >> event[i].t >> event[i].l >> event[i].m;
		mx = max(mx , event[i].l);
	}
	mx = max(mx , s);
	sort(event + 1 , event + n + 1 , cmp);
	event[n + 1].l = s;
	build(0 , 1 , 1 , mx);
	build(1 , 1 , 1 , mx);
    update(0 , 1 , 1 , mx , s , s * d);
	update(1 , 1 , 1 , mx , s ,  (-s) * u);
   
	for(int i = 1; i <= n + 1;  i++){
		int v1 = get(0 , 1 , 1 , mx , 1 , event[i].l);
		int v2 = get(1 , 1 , 1 , mx , event[i].l + 1 , mx);
		dp[i] = max(v1 - event[i].l * d + event[i].m , v2 + event[i].l * u + event[i].m);
	//	cout << "Debug" << " " << dp[i] << " " << event[i].t << " " << event[i].l << " " << event[i].m << " " << v1 << " "<< v2 << endl;
		update(0 , 1 , 1 , mx , event[i].l , dp[i] + event[i].l * d);
		update(1 , 1 , 1 , mx , event[i].l , dp[i] - event[i].l * u);
	}
	
	cout << dp[n + 1];
	
	
	
	
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}

• Subtask 1: 60 / 100