Submission #1109471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109471		michified	Long Distance Coach (JOI17_coach)	C++17	100 / 100	146 ms	27964 KiB

coach

#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
#define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

struct Line {
	mutable ll m, c, p;
	bool operator<(const Line& o) const {
		return m < o.m;
	}
	bool operator<(ll x) const {
		return p < x;
	}
};

struct lineContainer : multiset<Line, less<>> {
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 and a % b);
	}
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = lmx, 0;
		if (x->m == y->m) x->p = x->c > y->c ? lmx : lmn;
		else x->p = div(y->c - x->c, x->m - y->m);
		return x->p >= y->p;
	}
	void add(ll m, ll c) {
		auto z = insert({m, c, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() and isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() and (--x)->p >= y->p) isect(x, erase(y));
	}
	ll eval(ll x) {
		auto l = *lower_bound(x);
		return l.m * x + l.c;
	}
};

struct p_t {
	ll d, c;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, m, t, x, w, i;
	cin >> x >> n >> m >> w >> t;
	n++;
	vector<ll> s(n), d(m);
	for (i = 0; i < n - 1; i++) cin >> s[i];
	s[n - 1] = x;
	vector<p_t> ppl(m);
	for (i = 0; i < m; i++) cin >> ppl[i].d >> ppl[i].c;
	sort(s.rbegin(), s.rend());
	sort(ppl.begin(), ppl.end(), [](const auto& a, const auto& b){return a.d < b.d;});
	for (i = 0; i < m; i++) d[i] = ppl[i].d;
	vector<ll> pref(m + 1), last(m, lmx);
	lineContainer lc;
	for (i = 0; i < m; i++) pref[i + 1] = pref[i] + ppl[i].c;
	int tmp;
	for (i = 0; i < n; i++) {
		tmp = upper_bound(d.begin(), d.end(), s[i] % t) - d.begin() - 1;
		if (tmp >= 0) last[tmp] = s[i];
	}
	vector<ll> dp(m);
	lc.add(0, 0);
	for (i = 0; i < m; i++) {
		if (i > 0) dp[i] += dp[i - 1];
		dp[i] += ((x - d[i]) / t + 1) * w;
		if (last[i] != lmx) dp[i] = min(dp[i], pref[i + 1] + last[i] / t * (i + 1) * w - lc.eval(last[i] / t * w));
		lc.add(i + 1, pref[i + 1] - dp[i]);
	}
	cout << dp[m - 1] + (x / t + 1) * w;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29