Submission #1156792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156792		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	60 / 100	397 ms	49176 KiB

salesman

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <random>
#include <utility>
#include <variant>
#include <vector>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2>
inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2>
inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
#define int ll
const ll mod = 1e9 + 7;
const ll inf = 1e17;
const int MAX_N = 5e5 + 42;

const ll neutr = -inf;

struct SegmentTree {
	std::vector<ll> tree;

	void build(){
		tree.assign(4 * MAX_N, neutr);
	}

	void set(int ind, ll val, int x = 1, int lx = 0, int rx = MAX_N) {
		if(lx == rx){
			chkmax(tree[x], val);
			return;
		}
		int m = (lx + rx) >> 1;
		if(ind <= m) 
			set(ind, val, 2*x, lx, m);
		else 
			set(ind, val, 2*x + 1, m+1, rx);

		tree[x] = std::max(tree[2*x], tree[2*x + 1]);
	}

	ll query(int l, int r, int x = 1, int lx = 0, int rx = MAX_N) {
		if(l > rx || lx > r) return neutr;
		if(l <= lx && rx <= r) return tree[x];

		int m = (lx + rx) >> 1;
		ll left = query(l, r, 2*x, lx, m);
		ll right = query(l, r, 2*x + 1, m+1, rx);

		return std::max(left, right);
	}
};

SegmentTree segUp;
SegmentTree segDown;

std::vector< std::pair< int, std::pair< int, int > > > v;

signed main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL);
#endif

	int n, U, D, L;
	std::cin >> n >> U >> D >> L;

	for(int i = 1; i <= n; i++){
		int t, l, c;
		std::cin >> t >> l >> c;
		v.push_back({t, {l, c}});
	}

	v.push_back({ -1, { L, 0 } });
	v.push_back({ mod, { L, 0 } });

	std::sort(v.begin(), v.end());

	segUp.build();
	segDown.build();

	std::vector<ll> dp(MAX_N, neutr);
	dp[L] = 0;
	segUp.set(L, -L * U + dp[L]);
	segDown.set(L, L * D + dp[L]);

	for (int i = 1; i < (int)v.size(); ) {
		int day = v[i].first;
		int groupStart = i, groupEnd = i;
		while(groupEnd < (int)v.size() && v[groupEnd].first == day)
			groupEnd++;

		int cnt = groupEnd - groupStart;
		vector<int> pos(cnt);
		vector<ll> base(cnt, neutr);
		for (int j = 0; j < cnt; j++) {
			pos[j] = v[groupStart + j].second.first;
			ll cand1 = segUp.query(pos[j], MAX_N - 1) + pos[j] * U;
			ll cand2 = segDown.query(0, pos[j]) - pos[j] * D;
			base[j] = max(cand1, cand2);
		}

		vector<ll> bestVal = base;
		for (int j = 1; j < cnt; j++) {
			bestVal[j] = max(bestVal[j], bestVal[j-1] - D * (pos[j] - pos[j-1]));
		}
		for (int j = cnt - 2; j >= 0; j--) {
			bestVal[j] = max(bestVal[j], bestVal[j+1] - U * (pos[j+1] - pos[j]));
		}

		for (int j = 0; j < cnt; j++){
			int currPos = pos[j];
			ll new_dp = bestVal[j] + v[groupStart + j].second.second;
			chkmax(dp[currPos], new_dp);
			segUp.set(currPos, -currPos * U + dp[currPos]);
			segDown.set(currPos, currPos * D + dp[currPos]);
		}

		i = groupEnd;
	}

	std::cout << dp[L] << endl;
	return 0;
}

• Subtask 1: 60 / 100