Submission #1137828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137828		sano	Salesman (IOI09_salesman)	C++20	30 / 100	698 ms	84920 KiB

salesman

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

struct to {
	int t, a, w, ind;
};

bool zorad(to a, to b) {
	return a.a < b.a;
}

bool zorad2(to a, to b) {
	return a.t > b.t;
}

class intervalac {
	int n;
	vec<int> l, r, in;
	void update(int s) {
		in[s] = max(in[s * 2], in[s * 2 + 1]);
		return;
	}
public:
	intervalac(int vel) {
		n = 1;
		while (n < vel) n *= 2;
		l.resize(2 * n); r.resize(2 * n); in.resize(2 * n);
		For(i, n) {
			l[i + n] = i;
			r[i + n] = i;
			in[i + n] = (-1) * NEK;
		}
		rffor(i, 1, (n - 1)) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
			update(i);
		}
		return;
	}
	int daj(int a, int b, int s = 1) {
		if (l[s] > b || r[s] < a) return (-1) * NEK;
		if (a <= l[s] && r[s] <= b) return in[s];
		return max(daj(a, b, s * 2), daj(a, b, s * 2 + 1));
	}
	void zmen(int a, int k) {
		a += n;
		in[a] = k;
		a /= 2;
		while (a) {
			update(a);
			a /= 2;
		}
		return;
	}
};

void solve() {
	int n, u, d, s; cin >> n >> u >> d >> s;
	vec<to> p, p2;
	For(i, n) {
		int t, a, w; cin >> t >> a >> w;
		p.push_back({ t, a, w, i });
		p2.push_back({ t, a, w, i });
	}
	p.push_back({ NEK, s, 0, n });
	sort(p.begin(), p.end(), zorad);
	vec<int> i_p(n + 1, -1);
	For(i, p.size()) {
		i_p[p[i].ind] = i;
	}
	sort(p2.begin(), p2.end(), zorad2);
	intervalac seg1(p.size()), seg2(p.size());
	seg1.zmen(i_p[n], d * s);
	seg2.zmen(i_p[n], (-1) * u * s);
	For(i, p2.size()) {
		int o1 = seg1.daj(0, i_p[p2[i].ind]) - d * p2[i].a;
		int o2 = seg2.daj(i_p[p2[i].ind], p.size() - 1) + u * p2[i].a;
		int o = max(o1, o2);
		seg1.zmen(i_p[p2[i].ind], o + p2[i].w + d * p2[i].a);
		seg2.zmen(i_p[p2[i].ind], o + p2[i].w - u * p2[i].a);
	}
	int o = max(seg1.daj(0, i_p[n]) - d * s, seg2.daj(i_p[n], p.size() - 1) + u * s);
	cout << o << '\n';
	return;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
	return 0;
}

• Subtask 1: 30 / 100