Submission #931581

#	Time	Username	Problem	Language	Result	Execution time	Memory
931581		moonrabbit2	Salesman (IOI09_salesman)	C++17	60 / 100	191 ms	36048 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pii=array<int,2>;
using tii=array<int,3>;
const int N=5e5+5;
int n,s;
tii a[N];
ll U,D,S[N],dp[N];
struct Seg{
	ll F[N]={0};
	void init(){
		for(int i=1;i<=500001;i++) F[i]=-1e18;
	}
	void upd(int i,ll v){
		for(;i<=500001;i+=i&-i) F[i]=max(F[i],v);
	}
	ll qry(int i){
		ll r=-1e18;
		for(;i;i-=i&-i) r=max(r,F[i]);
		return r;
	}
}T1,T2;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>U>>D>>s;
	for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];
	sort(a+1,a+1+n);
	a[++n]={1000000000,s,0};
	T1.init(); T2.init();
	T1.upd(s,D*s); T2.upd(500002-s,-U*s);
	for(int l=1;l<=n;l++){
		int r=l;
		while(r+1<=n&&a[l][0]==a[r+1][0]) r++;
		ll mx=-1e18;
		S[l-1]=0;
		for(int i=l;i<=r;i++) S[i]=S[i-1]+a[i][2];
		for(int i=r;i>=l;i--){
			mx=max(mx,T1.qry(a[i][1])-D*a[i][1]-U*a[i][1]+S[i]);
			dp[i]=mx+U*a[i][1]-S[i-1];
			debug(i,dp[i]);
		}
		mx=-1e18;
		for(int i=l;i<=r;i++){
			mx=max(mx,T2.qry(500002-a[i][1])+U*a[i][1]+D*a[i][1]-S[i-1]);
			dp[i]=max(dp[i],mx-D*a[i][1]+S[i]);
		}
		for(int i=l;i<=r;i++){
			T1.upd(a[i][1],dp[i]+D*a[i][1]);
			T2.upd(500002-a[i][1],dp[i]-U*a[i][1]);
		}
		assert(l==r);
		l=r;
	}
	cout<<dp[n];
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
salesman.cpp:46:4: note: in expansion of macro 'debug'
   46 |    debug(i,dp[i]);
      |    ^~~~~

• Subtask 1: 60 / 100