Submission #931587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
931587	2024-02-22T06:09:59 Z	moonrabbit2	Salesman (IOI09_salesman)	C++17	100 / 100	188 ms	26052 KB

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],d[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=l;i<=r;i++) d[i]=max(T1.qry(a[i][1])-D*a[i][1],T2.qry(500002-a[i][1])+U*a[i][1]);
		for(int i=r;i>=l;i--){
			mx=max(mx,d[i]-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,d[i]+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]);
		}
		l=r;
	}
	cout<<dp[n];
	return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14936 KB	Output is correct
2	Correct	2 ms	14940 KB	Output is correct
3	Correct	2 ms	14940 KB	Output is correct
4	Correct	3 ms	14936 KB	Output is correct
5	Correct	4 ms	14940 KB	Output is correct
6	Correct	11 ms	15192 KB	Output is correct
7	Correct	20 ms	15192 KB	Output is correct
8	Correct	38 ms	20884 KB	Output is correct
9	Correct	57 ms	22976 KB	Output is correct
10	Correct	102 ms	25228 KB	Output is correct
11	Correct	111 ms	25172 KB	Output is correct
12	Correct	150 ms	25176 KB	Output is correct
13	Correct	142 ms	25172 KB	Output is correct
14	Correct	188 ms	25684 KB	Output is correct
15	Correct	174 ms	26052 KB	Output is correct
16	Correct	184 ms	25680 KB	Output is correct
17	Correct	2 ms	14940 KB	Output is correct
18	Correct	2 ms	14940 KB	Output is correct
19	Correct	2 ms	14940 KB	Output is correct
20	Correct	3 ms	14940 KB	Output is correct
21	Correct	3 ms	14940 KB	Output is correct
22	Correct	4 ms	14940 KB	Output is correct
23	Correct	4 ms	14808 KB	Output is correct
24	Correct	4 ms	14940 KB	Output is correct
25	Correct	37 ms	20944 KB	Output is correct
26	Correct	74 ms	23380 KB	Output is correct
27	Correct	121 ms	25236 KB	Output is correct
28	Correct	143 ms	25028 KB	Output is correct
29	Correct	173 ms	25808 KB	Output is correct
30	Correct	182 ms	25680 KB	Output is correct