Submission #530717

#	Time	Username	Problem	Language	Result	Execution time	Memory
530717		fhvirus	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2032 ms	10104 KiB

coach

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

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

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

int64_t dp[kN];

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] = pair<int64_t, int64_t>(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;

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

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

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