Submission #478038

#	Time	Username	Problem	Language	Result	Execution time	Memory
478038		pure_mem	Long Distance Coach (JOI17_coach)	C++14	100 / 100	350 ms	21464 KiB

coach

#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long 
#define MP make_pair

using namespace std;

const int MAXN = 2e5 + 5;
const ll INF = 1e18;

struct Line {
	ll k, b;
	mutable function<const Line* ()> getNext;
	ll get(ll x) {
		return k * x + b;
	}
	double inters(const Line& oth) const {
		return (b - oth.b) * 1.0 / (oth.k - k);
	}
	bool operator< (const Line& oth) const {
		if(oth.k != INF) return k > oth.k;
		const Line* nxt = getNext();
		if(nxt == 0) return 0;
		return b - nxt->b >= (nxt->k - k) * oth.b;
	}
};

struct CHT: public multiset<Line> {
	bool bad(iterator y) {
		auto z = next(y);
		if(y == begin()) {
			if(z == end()) return 0;
			return y->k == z->k && y->b >= z->b;
		}
		auto x = prev(y);
		if (z == end()) return y->k == x->k && y->b >= x->b;
		return 1.0 * (x->b - y->b) * (z->k - x->k) >= 1.0 * (x->b - z->b) * (y->k - x->k);
	}
	void add(ll k, ll b) {
		auto it = insert((Line){k, b});
		it->getNext = [=] { return next(it) == end() ? 0 : &*next(it); };
		if(bad(it)) return void(erase(it));
		while(next(it) != end() && bad(next(it))) erase(next(it));
		while(it != begin() && bad(prev(it))) erase(prev(it));
	}
	ll get(ll x) {
		Line me = *lower_bound((Line){INF, x});
		return me.get(x);
	}
}cht;

int n, m;
ll len, w, t, water[MAXN], dp[MAXN], pr[MAXN];
pair<ll, ll> men[MAXN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> len >> n >> m >> w >> t;

	for(int i = 1;i <= n;i++)
		cin >> water[i];
	water[++n] = len;
	sort(water + 1, water + n + 1, [](ll a, ll b) {return a % t < b % t;});
	for(int i = 1;i <= m;i++)
		cin >> men[i].X >> men[i].Y;
	sort(men + 1, men + m + 1);
	for(int i = m;i >= 1;i--)
		pr[i] = pr[i + 1] + men[i].Y;
	for(int p1 = n, p2 = m;p2;p2--) {
		while(p1 && water[p1] % t > men[p2].X) {
			ll cost = water[p1] / t * w;
			cht.add(-cost, dp[p2 + 1] - pr[p2 + 1] + (p2 + 1) * cost);
			p1--;
		}
		dp[p2] = dp[p2 + 1] + (len - men[p2].X) / t * w + w;
		if(!cht.empty())
			dp[p2] = min(dp[p2], cht.get(p2) + pr[p2]);
		//cerr << p2 << " " << dp[p2] << "\n";
	}
	cout << dp[1] + len / t * w + w;
	return 0;
}

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