Submission #1007904

#TimeUsernameProblemLanguageResultExecution timeMemory
1007904beabossLong Distance Coach (JOI17_coach)C++14
71 / 100
2064 ms24696 KiB
// Source: https://oj.uz/problem/view/JOI17_coach?locale=en
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;
#define int long long

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int INF = 1e9;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int x, n, m, w, t;
	cin >> x >> n >> m >> w >> t;
	m++;

	vector<array<int, 3> > all(n + m + 1, {-1, -1, 1});

	FOR(i, 1, n + 1) {
		cin >> all[i][1];
		all[i][0] = all[i][1] % t;
		all[i][2] = 0;
	}	
	FOR(i, n + 1, n + m) cin >> all[i][0] >> all[i][1];	
	all[n + m] = {x % t, x, 0};


	sort(all.begin(), all.end());

	vi prefc(n + m + 1, 0);
	vi cnt(n + m + 1, 0);
	for (int i = 1; i <= n + m; i++) {
		prefc[i] = prefc[i-1] + all[i][1] * all[i][2];
		cnt[i] = cnt[i-1] + all[i][2];
	}
	vi dp(n + m + 1, 0);
	int periods = (x / t);

	for (int i = 1; i <= n + m; i++) {
		// cout << all[i][0] << ' ' << all[i][1] << ' ' << all[i][2] << endl;
		if (all[i][2] == 0) { // refill point
			dp[i] = dp[i-1];
			for (int j = 0; j < i; j++) {

				int skip = (all[i][1] - all[i][0]) / t;
				// if (all[i][0] == 9) cout << j << ' ' << prefc[i] - prefc[j] << endl;

				ckmin(dp[i], prefc[i] - prefc[j] + dp[j] + skip * w * (cnt[i] - cnt[j]));
			}
		} else {
			// cout << all[i][0] <<
			dp[i] = dp[i-1] + w * (periods + (all[i][0] <= (x % t)));
		}
		// cout << dp[i] << endl;
	}

	cout << dp[n + m] + (periods + 1ll) * w << endl;




}












#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...