제출 #441442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441442		dutch	Salesman (IOI09_salesman)	C++17	100 / 100	682 ms	37616 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p a[i][1]

const int INF = 1e18, H = 5e5+2;

void z(int &a, int b){ a = max(a, b); }

template<class T> struct SegmentTree{
	const T ID = -INF;
	int n = 1, i; vector<T> a;
	SegmentTree(int N){ while((n+=n)<N); a.assign(2*n, ID); }
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(T v){
		for(z(a[i], v); i/=2; ) a[i] = max(a[2*i], a[2*i+1]); }
	T operator()(int l, int r){
		T x = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) x = max(x, a[l++]);
			if(r & 1) x = max(x, a[--r]);
		}
		return x;
	}
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	int n, u, d, s; cin >> n >> u >> d >> s;
	d = -d, u = -u;
	array<int, 3> a[n]; // day, location, profitability
	for(auto &i : a){
		cin >> i[0] >> i[1] >> i[2];
	}
	sort(a, a+n);

	SegmentTree<int> dpD(H), dpU(H);
	dpD[s] = s * d, dpU[s] = - s * u;

	for(int l=0; l<n; ){
		int r = l+1;
		while(r<n && a[l][0] == a[r][0]) ++r;

		for(int i=l; i<r; ++i){
			a[i][0] = -INF;
			z(a[i][0], dpD(p, H) - p * d);
			z(a[i][0], p * u + dpU(0, p));
			// cout << i+1 sp p sp a[i][0] nl;
		}

		int pre = -INF, suf = -INF, sum = 0;

		for(int i=l; i<r; ++i){
			z(pre, a[i][0] - p * u - sum);
			sum += a[i][2];
			dpD[p] = (pre + sum + p * u) + p * d;
			dpU[p] = (pre + sum + p * u) - p * u;
		}

		sum = 0;

		for(int i=r-1; i>=l; --i){
			z(suf, a[i][0] + p * d - sum);
			sum += a[i][2];
			dpD[p] = (suf + sum - p * d) + p * d;
			dpU[p] = (suf + sum - p * d) - p * u;
		}

		l = r;
	}

	int ans = 0;
	ans = max(ans, dpD(s, H) - s * d);
	ans = max(ans, dpU(0, s) + s * u);
	cout << ans;
}

• Subtask 1: 100 / 100