Submission #530724

#	Time	Username	Problem	Language	Result	Execution time	Memory
530724		fhvirus	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2083 ms	10292 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 sc[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] = 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;

	for (int i = M - 1, j = N; i >= 0; --i) {
		for (; j >= 0; --j) {
			int r = prev_passenger[j];
			if (r < i) break;
			sc[j] = 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));
		for (int k = N; k > j; --k)
			dp[i] = min(dp[i], get(sc[k], 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: 0 / 29