Submission #407356

#	Time	Username	Problem	Language	Result	Execution time	Memory
407356		AugustinasJucas	Salesman (IOI09_salesman)	C++14	15 / 100	3093 ms	48344 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
int n, U, D, s;
const int dydis = 5e5 + 10;
vector<pair<int, int> > fairs[dydis];
long long curAns[dydis];
long long v1[dydis], v2[dydis];
void updateCur(int ind, long long x){
	curAns[ind] = x;
	//[curAns[y]+u*y]
	v1[ind] = curAns[ind] + 1ll * U * ind;
	v2[ind] = curAns[ind] - 1ll * D * ind;
}	
long long fMx1(int l, int r){
	long long ret = -inf;
	for(int i = l; i <= r; i++) ret = max(ret, v1[i]);
	return ret;
}
long long fMx2(int l, int r){
	long long ret = -inf;
	for(int i = l; i <= r; i++) ret = max(ret, v2[i]);
	return ret;
}
void daryk(int d){
	if(fairs[d].size() == 0) return;
	int kurMax = -1;
	int lastFair = -1;
	long long pref = 0;
	vector<pair<int, long long> > chang;
	//cout << "darom " << d << "-aja diena!" << endl;
	for(auto x : fairs[d]){
		long long bv = (kurMax == -1 ? -inf : 1ll * curAns[kurMax] - 1ll * (x.first - kurMax) * U + pref); 
		long long galiBut = fMx1(lastFair+1, x.first-1) - 1ll * x.first * U; 
		// y(ind) is [last+1;  x.first-1],
		// kad A = curAns[y]-(x.first-y) * u butu didziausias ir A > bv
		// A = [curAns[y]+u*y] - [x.first*u]
		//      ^^^^^^^^^^^^^ rasti sita max intervale y [last+1; x.first-1]
		//cout << "bv = " << bv << ", galiButi = " << galiBut <<", pl = " << x.second << endl;
		
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = x.first;
			pref = 0;
		}
		pref += x.second;
		lastFair = x.first;
	}
	lastFair = dydis-1;
	kurMax = dydis-1;
	pref = 0;
	for(int i = (int)fairs[d].size()-1; i > -1; i--){
		auto x = fairs[d][i];
		long long bv = (kurMax == dydis-1 ? -inf : 1ll * curAns[kurMax] - 1ll * (kurMax - x.first) * D + pref);
		long long galiBut = fMx2(x.first+1, lastFair-1) + 1ll * x.first * D;
	//	cout << "FMX2 = " << fMx2(x.first+1, lastFair-1) <<", dar pridesiu " << x.first * D << ", xf = " << x.first << ", d = " << D<<endl;
	//	cout << "bv = " << bv << ", galiButi = " << galiBut <<", pl = " << x.second << endl;
		// y(ind) is [x.first+1;  x.last-1],
		// kad A = curAns[y]-(y-x.first) * d butu didziausias ir A > bv
		// A = [curAns[y]-d*y] + [x.first*u]
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = x.first;
			pref = 0;
		}
		pref += x.second;
		lastFair = x.first;
	}
	for(auto x : chang){
		int ind = x.first;
		long long val = x.second;
	//	cout << "norim " << ind << " pakeisti i " << val << endl;
		if(val < curAns[ind]){
			continue;
		}
		updateCur(ind, val);
	}
}
int main(){
	for(int i = 0; i < dydis; i++) curAns[i] = v1[i] = v2[i] = -inf;
	cin >> n >> D >> U >> 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 * (s > i ? U : D) * abs(s-i));
	}
	cout << ans;
	return 0;
}

• Subtask 1: 15 / 100