제출 #1306769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306769		liangjeremy	Salesman (IOI09_salesman)	C++20	60 / 100	380 ms	47420 KiB

salesman

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sint=__int128;
using lb=long double;
mt19937 rng(random_device{}()); 

struct node{
	int d; int l; int m; //day loc make
};
bool cmp(node a, node b){
	return a.d<b.d; 
}

struct segtree{
	vector<int>mx; const int maxn=5e5+10;
	segtree(){ mx.resize(maxn<<2,-1e18); }
	void update(int l, int r, int rt, int idx, int val){
		if(l==r){
			mx[rt]=max(mx[rt],val); return; 
		}
		int mid=(l+r)>>1; 
		if(idx<=mid)update(l,mid,rt<<1,idx,val); 
		else update(mid+1,r,rt<<1|1,idx,val); 
		mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); 
	}
	int query(int l, int r, int rt, int L, int R){
		if(L<=l && r<=R)return mx[rt];
		int ans=-1e18; int mid=(l+r)>>1; 
		if(L<=mid)ans=max(ans,query(l,mid,rt<<1,L,R)); 
		if(R>mid)ans=max(ans,query(mid+1,r,rt<<1|1,L,R)); 
		return ans; 
	}
};

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,l,r,s; cin>>n>>l>>r>>s; vector<node>a(n+1); a[0]={0,s,0}; a.push_back({(int)1e18,s,0}); 
	for(int i=1; i<=n; i++){ cin>>a[i].d>>a[i].l>>a[i].m; }
	sort(a.begin(),a.end(),cmp); vector<int>dp(n+2,-1e18); dp[0]=0; const int maxn=5e5+5; 
	segtree segl; segtree segr; segl.update(1,maxn,1,a[0].l,dp[0]+r*a[0].l); segr.update(1,maxn,1,a[0].l,dp[0]-l*a[0].l);
	for(int i=1; i<=n+1; i++){
		dp[i]=max(dp[i],segl.query(1,maxn,1,1,a[i].l)+a[i].m-r*a[i].l); 
		dp[i]=max(dp[i],segr.query(1,maxn,1,a[i].l+1,maxn)+a[i].m+l*a[i].l); 
		segl.update(1,maxn,1,a[i].l,dp[i]+r*a[i].l); segr.update(1,maxn,1,a[i].l,dp[i]-l*a[i].l); 
	}
	cout<<dp.back(); 
}
/*
Overhead the albatross hangs motionless upon the air
And deep beneath the rolling waves in labyrinths of coral caves
The echo of a distant time comes willowing across the sand
And everything is green and submarine
 
And no one showed us to the land
And no one knows the wheres or whys
But something stirs and something tries
And starts to climb towards the light
*/

• Subtask 1: 60 / 100