oj.uz

Submission #931580

# Submission time Handle Problem Language Result Execution time Memory
931580 2024-02-22T06:00:15 Z moonrabbit2 Salesman (IOI09_salesman) C++17
62 / 100
 187 ms 30804 KB 
#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]);
		}
		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:46:4: note: in expansion of macro 'debug'
   46 |    debug(i,dp[i]);
      |    ^~~~~

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 4 ms 12888 KB Output is correct
6 Correct 9 ms 13148 KB Output is correct
7 Correct 20 ms 13660 KB Output is correct
8 Correct 38 ms 20816 KB Output is correct
9 Correct 56 ms 21328 KB Output is correct
10 Correct 103 ms 25684 KB Output is correct
11 Correct 111 ms 26424 KB Output is correct
12 Correct 139 ms 27220 KB Output is correct
13 Correct 144 ms 27336 KB Output is correct
14 Correct 183 ms 30804 KB Output is correct
15 Correct 187 ms 30064 KB Output is correct
16 Correct 181 ms 29776 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Incorrect 3 ms 12892 KB Output isn't correct
19 Incorrect 2 ms 12892 KB Output isn't correct
20 Incorrect 3 ms 12892 KB Output isn't correct
21 Incorrect 3 ms 12892 KB Output isn't correct
22 Incorrect 4 ms 12892 KB Output isn't correct
23 Incorrect 4 ms 12892 KB Output isn't correct
24 Incorrect 4 ms 12892 KB Output isn't correct
25 Incorrect 42 ms 20288 KB Output isn't correct
26 Incorrect 71 ms 21880 KB Output isn't correct
27 Incorrect 122 ms 25428 KB Output isn't correct
28 Incorrect 131 ms 26292 KB Output isn't correct
29 Incorrect 184 ms 28312 KB Output isn't correct
30 Incorrect 185 ms 29268 KB Output isn't correct