Submission #283088

#	Time	Username	Problem	Language	Result	Execution time	Memory
283088		maximath_1	Long Distance Coach (JOI17_coach)	C++11	100 / 100	205 ms	26232 KiB

coach

#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll x, w, t; int n, m;
ll s[200005], pref[200005], d[200005];
pair<ll, ll> p[200005];
ll v[200005];

bool Q;
struct Line{
	mutable ll m, c, pt;
	bool operator<(const Line& rhs) const{
		return Q ? pt < rhs.pt : m < rhs.m;
	}
};
 
struct LineContainer : multiset<Line>{
	const ll inf = LLONG_MAX;

	ll div(ll a, ll b){
		return a / b - ((a ^ b) < 0 && a % b);
	}

	bool isect(iterator x, iterator y) {
		if(y == end()){ 
			x -> pt = inf; 
			return false;
		}
		if(x -> m == y -> m) 
			x -> pt = x -> m > y -> m ? inf : -inf;
		else 
			x -> pt = div(y -> c - x -> c, x -> m - y -> m);
		return x -> pt >= y -> pt;
	}

	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() && isect(-- x, y)) isect(x, y = erase(y));
		while((y = x) != begin() && (-- x) -> pt >= y -> pt)
			isect(x, erase(y));
	}

	ll query(ll x){
		Q = 1; auto l = *lower_bound({0, 0, x}); Q = 0;
		return l.m * x + l.c;
	}
} cht;

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

	cin >> x >> n >> m >> w >> t;
	for(int i = 1; i <= n; i ++) cin >> s[i];
	s[n + 1] = x;
	sort(s + 1, s + n + 2); reverse(s + 1, s + n + 2);

	for(int i = 1; i <= m; i ++) cin >> p[i].first >> p[i].second;
	sort(p + 1, p + m + 1);
	for(int i = 1; i <= m; i ++){
		d[i] = p[i].first;
		pref[i] = pref[i - 1] + p[i].second;
	}

	for(int i = 1; i <= n + 1; i ++)
		v[lower_bound(d + 1, d + m + 1, s[i] % t) - d - 1] = s[i];

	ll ans = 0ll;
	cht.add(0, 0);

	for(int i = 1; i <= m; i ++){
		ans += (x - d[i]) / t * w + w;
		if(v[i]) ans = min(ans, -cht.query(v[i] / t * w) + v[i] / t * w * i + pref[i]);
		cht.add(i, pref[i] - ans);
	}

	ans += x / t * w + w;

	cout << ans << endl;
	return 0;
}

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