제출 #210097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210097		hanagasumi	Long Distance Coach (JOI17_coach)	C++17	0 / 100	5 ms	376 KiB

coach

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;
typedef long double ld;


signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int x, n, m, w, T;
	cin >> x >> n >> m >> w >> T;
	vector<int> s(n + 1);
	vector<pair<int, int>> p(m);
	vector<int> pref(m + 1, 0);
	vector<int> cnt(m + 1, 0);
	vector<int> d(m + 1, 0);
	s[0] = 0;
	for (int i = 1; i <= n; i++) 
		cin >> s[i];	
	s.pb(x);
	n += 2;

	for (int i = 0; i < m; i++) {
		cin >> p[i].ft >> p[i].sc;
	}
	sort(p.begin(), p.end());
	for (int i = 0; i < m; i++) {
		pref[i + 1] = pref[i] + p[i].sc;
		cnt[i] = (x - p[i].ft) / T + 1;
		d[i] = p[i].ft;
	}

	vector<vector<pair<int, int>>> can(m + 1);

	for (int i = 1; i < n; i++) {
		int driver = s[i] / T * T;
		int lstt = -1, lst = -1;
		for (int j = 0; j < m; j++) {
			int time = s[i] / T * T + d[j];
			if(time > s[i]) 
				time -= T;
			if(time < s[i - 1])
				continue;
			if(time < driver) 
				continue;
			if(time > lstt) {
				lstt = time;
				lst = j;
			} 
			else 
				return -1;
		}
		if(lstt == -1) 
			continue;
		for (int j = m - 1; j >= 0; j--) {
			int time = s[i] / T * T + d[j];
			if(time > s[i]) 
				time -= T;
			if(time < s[i - 1]) 
				continue;
			if(time < driver) 
				continue;
			can[lst].pb({s[i], j});
		}
	}
	vector<int> dp(m + 1, 0);
	for (int i = 0; i < m; i++) {
		dp[i + 1] = dp[i] + cnt[i] * w;
		int add = 0;
		for (auto x : can[i]) {
			if(x.sc == i) 
				add = 0;
			int time = x.ft / T * T + d[x.sc];
			if(time > x.ft) 
				time -= T;
			add += time / T * w + p[x.sc].sc;
			dp[i + 1] = min(dp[i + 1], dp[x.sc] + add);
		}
	}
	cout << dp[m] + (((x  - 1) / T + 1) * w) << endl;


	return 0;
}

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