Submission #133606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
133606	2019-07-21T06:21:23 Z	figter001	Salesman (IOI09_salesman)	C++17	60 / 100	958 ms	37784 KB

salesman

#include <bits/stdc++.h>

using namespace std;

#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int nax = 5e5 + 100;

int d[nax],l[nax],m[nax];
int n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];

void build(int n,int s,int e){
	if(s == e){
		up[n] = dp[s] + s * U;
		dn[n] = dp[s] - s * D;
		return;
	}
	build(n*2,s,(s+e)/2);
	build(n*2+1,(s+e)/2+1,e);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

void update(int n,int s,int e,int at){
	if(s > at || e < at)return;
	if(s == e){
		up[n] = dp[s] - s * U;
		dn[n] = dp[s] + s * D;
		return;
	}
	update(n*2,s,(s+e)/2,at);
	update(n*2+1,(s+e)/2+1,e,at);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

ll get(int n,int s,int e,int l,int r,int t){
	if(s > r || e < l)return -1e18;
	if(s >= l && e <= r){
		if(t == 0)return up[n];
		else if(t == 1)return dn[n];
	}
	return max( get(n*2,s,(s+e)/2,l,r,t) , get(n*2+1,(s+e)/2+1,e,l,r,t) );
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout << fixed;
	cin>>n>>U>>D>>s;
	n+=2;
	d[0] = -1;l[0] = s;
	d[n-1] = nax + 1;l[n-1] = s;
	len = s;
	for(int i=1;i<n;i++){
		cin>>d[i]>>l[i]>>m[i];
		len = max(len,l[i]);
	}
	len++;
	vector<int> idx;
	for(int i=0;i<n;i++)idx.push_back(i);
	sort(idx.begin(),idx.end(), [&] (int a,int b) {
		return d[a] < d[b];
	});
	for(int i=1;i<=len;i++)dp[i] = -1e10;
	dp[s] = 0;
	build(1,1,len);
	for(int i : idx){
		ll cur = -1e18;
		if(i != 0){
			cur = max(cur, get(1,1,len,1,l[i],1) + m[i] - D*l[i]);
			cur = max(cur, get(1,1,len,l[i],len,0) + m[i] + U*l[i]);
		}
		dp[l[i]] = max(dp[l[i]],cur);
		update(1,1,len,l[i]);
	}
	cout << dp[s] << endl;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	632 KB	Output is correct
4	Correct	4 ms	504 KB	Output is correct
5	Correct	6 ms	888 KB	Output is correct
6	Correct	53 ms	21496 KB	Output is correct
7	Correct	110 ms	22516 KB	Output is correct
8	Correct	198 ms	24312 KB	Output is correct
9	Correct	283 ms	25712 KB	Output is correct
10	Correct	513 ms	30280 KB	Output is correct
11	Correct	586 ms	30952 KB	Output is correct
12	Correct	761 ms	33252 KB	Output is correct
13	Correct	773 ms	33640 KB	Output is correct
14	Correct	947 ms	37784 KB	Output is correct
15	Correct	872 ms	36716 KB	Output is correct
16	Correct	958 ms	36844 KB	Output is correct
17	Incorrect	2 ms	376 KB	Output isn't correct
18	Incorrect	2 ms	504 KB	Output isn't correct
19	Incorrect	3 ms	504 KB	Output isn't correct
20	Incorrect	5 ms	632 KB	Output isn't correct
21	Incorrect	4 ms	632 KB	Output isn't correct
22	Incorrect	6 ms	888 KB	Output isn't correct
23	Incorrect	7 ms	888 KB	Output isn't correct
24	Incorrect	6 ms	888 KB	Output isn't correct
25	Incorrect	186 ms	23768 KB	Output isn't correct
26	Incorrect	349 ms	26864 KB	Output isn't correct
27	Incorrect	612 ms	30952 KB	Output isn't correct
28	Incorrect	638 ms	31848 KB	Output isn't correct
29	Incorrect	923 ms	35284 KB	Output isn't correct
30	Incorrect	882 ms	36204 KB	Output isn't correct