Submission #818769

#	Time	Username	Problem	Language	Result	Execution time	Memory
818769		yellowtoad	Salesman (IOI09_salesman)	C++17	100 / 100	1201 ms	56956 KiB

salesman

#include <iostream>
#include <algorithm>
#define f first
#define s second
using namespace std;

const long long n = 5e5+1;
long long m, u, d, st, node[2][2000010], dp[2][500010], lst;
pair<long long,pair<long long,long long>> event[2][500010];

void build(int i, int id, int x, int y) {
	if (x == y) {
		if (x == st) {
			if (i == 0) node[i][id] = -u*st;
			else node[i][id] = -d*(n-st);
		} else node[i][id] = -1e18;
		return;
	}
	int mid = (x+y)/2;
	build(i,id*2,x,mid);
	build(i,id*2+1,mid+1,y);
	node[i][id] = max(node[i][id*2],node[i][id*2+1]);
}

long long query(int i, int id, int x, int y, int l, int r) {
	if ((l <= x) && (y <= r)) return node[i][id];
	if ((y < l) || (r < x)) return -1e18;
	int mid = (x+y)/2;
	return max(query(i,id*2,x,mid,l,r),query(i,id*2+1,mid+1,y,l,r));
}

void update(int i, int id, int x, int y, int pos, long long val) {
	if (x == y) {
		if (i == 0) node[i][id] = max(node[i][id],val-u*pos);
		else node[i][id] = max(node[i][id],val-d*(n-pos));
		return;
	}
	int mid = (x+y)/2;
	if (pos <= mid) update(i,id*2,x,mid,pos,val);
	else update(i,id*2+1,mid+1,y,pos,val);
	node[i][id] = max(node[i][id*2],node[i][id*2+1]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> m >> u >> d >> st;
	for (int i = 1; i <= m; i++) {
		cin >> event[0][i].f >> event[0][i].s.f >> event[0][i].s.s;
		event[1][i] = event[0][i];
		event[1][i].s.f = -event[1][i].s.f;
	}
	sort(event[0]+1,event[0]+m+1);
	sort(event[1]+1,event[1]+m+1);
	for (int i = 1; i <= m; i++) event[1][i].s.f = -event[1][i].s.f;
	build(0,1,1,n);
	build(1,1,1,n);
	for (int i = 1; i <= m; i++) {
		if (event[0][i].f != event[0][i-1].f) {
			if (lst) {
				for (int k = 0; k <= 1; k++) {
					for (int j = lst; j < i; j++) {
						update(0,1,1,n,event[k][j].s.f,dp[k][j]);
						update(1,1,1,n,event[k][j].s.f,dp[k][j]);
					}
				}
			}
			long long pos = event[0][i].s.f, val = event[0][i].s.s;
			dp[0][i] = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
			pos = event[1][i].s.f, val = event[1][i].s.s;
			dp[1][i] = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
			lst = i;
		} else {
			long long pos = event[0][i].s.f, val = event[0][i].s.s;
			long long pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
			dp[0][i] = max(pro,dp[0][i-1]+val-d*(pos-event[0][i-1].s.f));
			pos = event[1][i].s.f, val = event[1][i].s.s;
			pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
			dp[1][i] = max(pro,dp[1][i-1]+val-u*(event[1][i-1].s.f-pos));
		}
	}
	for (int k = 0; k <= 1; k++) {
		for (int j = lst; j <= n; j++) {
			update(0,1,1,n,event[k][j].s.f,dp[k][j]);
			update(1,1,1,n,event[k][j].s.f,dp[k][j]);
		}
	}
	long long pos = st, val = 0;
	long long pro = max(query(0,1,1,n,pos,pos)+(u*pos),max(query(0,1,1,n,pos+1,n)+(u*pos)+val,query(1,1,1,n,1,pos-1)+(d*(n-pos))+val));
	update(0,1,1,n,pos,pro);
	update(1,1,1,n,pos,pro);
	cout << query(0,1,1,n,pos,pos)+(u*pos) << endl;
}

• Subtask 1: 100 / 100