제출 #409194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409194		AugustinasJucas	Salesman (IOI09_salesman)	C++14	60 / 100	1328 ms	65536 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
struct medis{
	struct node{
		long long val = -inf;
		int l, r;
	};
	vector<node> mas;
	int n;
	int dbInd = 0;
	void build(int v){
		if(v >= n){
			mas[v].l = mas[v].r = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			mas[v].l = mas[v*2].l;
			mas[v].r = mas[v*2+1].r;
		}
	}
	medis(int dd){
		n = dd;
		mas.resize(2 * n + 1);
		build(1);
	}
	void change(int v, int l, int r, long long x){
		if(l <= mas[v].l && mas[v].r <= r){
			mas[v].val = x;
		}else if(r < mas[v].l || mas[v].r < l){
			return;
		}else{
			change(v*2, l, r, x);
			change(v*2+1, l, r, x);
			mas[v].val = max(mas[v*2].val, mas[v*2+1].val);
		}
	}
	long long get(int v, int l, int r){
		if(l <= mas[v].l && mas[v].r <= r){
			return mas[v].val;
		}else if(r < mas[v].l || mas[v].r < l){
			return -inf;
		}else{
			return max(get(v*2, l, r), get(v*2+1, l, r));
		}
	}
};
 
int n, U, D, s;
const int dydis = 5e5 + 10;
vector<pair<int, int> > fairs[dydis];
long long curAns[dydis];
medis v1(dydis), v2(dydis);
void updateCur(int ind, long long x){
	curAns[ind] = x;
	v1.change(1, ind, ind, curAns[ind] + 1ll * D * ind);
	v2.change(1, ind, ind, curAns[ind] - 1ll * U * ind);
}	
long long fMx1(int l, int r){
	return v1.get(1, l, r);
}
long long fMx2(int l, int r){
	return v2.get(1, l, r);
}
void daryk(int d){
	if(fairs[d].size() == 0) return;
	vector<pair<int, long long> > chang;
	for(auto x : fairs[d]){
		long long galiBut = fMx1(0, x.first-1) - 1ll * x.first * D; 
		chang.push_back({x.first,  galiBut + x.second});
	}
	for(int i = (int)fairs[d].size()-1; i > -1; i--){
		auto x = fairs[d][i];
		long long galiBut = fMx2(x.first+1, dydis-1) + 1ll * x.first * U;
		chang.push_back({x.first, galiBut + x.second});
	}
	for(auto x : chang){
		int ind = x.first;
		long long val = x.second;
		if(val < curAns[ind]){
			continue;
		}
		updateCur(ind, val);
	}
}
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	for(int i = 0; i < dydis; i++) curAns[i] = -inf;
	cin >> n >> U >> D >> s;
	
	updateCur(s, 0);
	for(int i = 0; i < n; i++){
		int t, l, p; cin >> t >> l >> p;
		fairs[t].push_back({l, p});
	}
	for(int i = 0; i < dydis; i++){
		sort(fairs[i].begin(), fairs[i].end());
	}
	for(int i = 0; i < dydis; i++){
		daryk(i);
	}
	long long ans = 0;
	for(int i = 0; i < dydis; i++){
		ans = max(ans, curAns[i] - 1ll * (i < s ? D : U) * abs(s-i));
	}
	cout << ans;
	return 0;
}

• Subtask 1: 60 / 100