Submission #530728

#	Time	Username	Problem	Language	Result	Execution time	Memory
530728		fhvirus	Long Distance Coach (JOI17_coach)	C++17	100 / 100	172 ms	23940 KiB

coach

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

typedef pair<int64_t, int64_t> pii;
int64_t get (const pii& p, const int64_t& v)
{ return p.first * v + p.second; }

const int kN = 200'002;
int N, M;
int64_t X, W, T;
pii refill[kN], passenger[kN];

int64_t preC[kN];
int prev_passenger[kN];

int64_t dp[kN];

pii nd[kN * 4];
void insert(pii p, int i = 1, int l = 0, int r = M) {
	if (l >= r) return;
	int m = (l + r) / 2;
	if (get(p, m) < get(nd[i], m))
		swap(p, nd[i]);
	if (l + 1 == r) return;
	if (nd[i].first < p.first) insert(p, i * 2, l, m);
	if (nd[i].first > p.first) insert(p, i * 2 + 1, m + 1, r);
}
int64_t query(int p, int i = 1, int l = 0, int r = M) {
	if (l >= r) return LLONG_MAX;
	int m = (l + r) / 2;
	if (l + 1 == r or p == m) return get(nd[i], p);
	return min(get(nd[i], p), p < m ? query(p, i * 2, l, m) : query(p, i * 2 + 1, m + 1, r));
}

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

	cin >> X >> N >> M >> W >> T;
	for (int i = 0; i < N; ++i) {
		int64_t S; cin >> S;
		refill[i].first = S % T;
		refill[i].second = S / T;
	}
	for (int i = 0; i < M; ++i) {
		cin >> passenger[i].first;
		cin >> passenger[i].second;
	}

	refill[N] = pii(X % T, X / T);
	sort(refill, refill + N + 1);
	sort(passenger, passenger + M);
	for (int i = 0; i <= N; ++i)
		prev_passenger[i] = lower_bound(passenger, passenger + M, refill[i]) - passenger - 1;
	for (int i = 0; i < M; ++i)
		preC[i + 1] = preC[i] + passenger[i].second;
	fill(nd, nd + M * 4, pii(0, LLONG_MAX));

	for (int i = M - 1, j = N; i >= 0; --i) {
		for (; j >= 0; --j) {
			int r = prev_passenger[j];
			if (r < i) break;
			insert(pii(-W * refill[j].second, preC[r + 1] + dp[r + 1] + W * (r + 1) * refill[j].second));
		}
		dp[i] = dp[i + 1] + W * (X / T + (passenger[i].first % T < X % T));
		dp[i] = min(dp[i], query(i) - preC[i]);
	}

	cout << dp[0] + W * (X / T + 1) << '\n';
	return 0;
}

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