제출 #530724

#제출 시각아이디문제언어결과실행 시간메모리
530724fhvirusLong Distance Coach (JOI17_coach)C++17
71 / 100
2083 ms10292 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...