Submission #422821

#	Time	Username	Problem	Language	Result	Execution time	Memory
422821		cgiosy	Salesman (IOI09_salesman)	C++17	62 / 100	510 ms	31684 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
constexpr int M=500002;

struct pii {
	int x, v;
	bool operator<(pii b) const { return x<b.x; }
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, L, R, st;
	cin>>N>>L>>R>>st;
	vector<pii> A[M];
	for(int i=0; i<N; i++) {
		int t, x, v;
		cin>>t>>x>>v;
		A[t].push_back({x, v});
	}
	auto set=[&](int* T, int i, int x) {
		for(; i<M; i+=i&-i) T[i]=max(T[i], x);
	};
	auto qry=[&](int* T, int i) {
		int x=-2e9;
		for(; i; i-=i&-i) x=max(x, T[i]);
		return x;
	};
	int T1[M], T2[M];
	fill(T1, T1+M, -2e9);
	fill(T2, T2+M, -2e9);
	set(T1, st, st*L);
	set(T2, M-st, -st*R);
	for(auto&X:A) if(int n=X.size()) {
		sort(X.begin(), X.end());
		int D[n];
		for(int i=0, m=-2e9, p=0; i<n; i++) {
			auto[x,v]=X[i];
			D[i]=m=max({m+v-(x-p)*R, qry(T1, x)+(v-x*L), qry(T2, M-x)+(v+x*R)});
		}
		for(int i=n-1, m=-2e9, p=0; i>=0; i--) {
			auto[x,v]=X[i];
			m=max({D[i], qry(T1, x)+(v-x*L), qry(T2, M-x)+(v+x*R)});
			set(T1, x, m+x*L);
			set(T2, M-x, m-x*R);
		}
	}
	cout<<max(qry(T1, st)-st*L, qry(T2, M-st)+st*R)<<'\n';
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:39:26: warning: unused variable 'p' [-Wunused-variable]
   39 |   for(int i=n-1, m=-2e9, p=0; i>=0; i--) {
      |                          ^

• Subtask 1: 62 / 100