Submission #431599

#	Time	Username	Problem	Language	Result	Execution time	Memory
431599		oolimry	Long Distance Coach (JOI17_coach)	C++17	71 / 100	250 ms	86084 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
	
lint X, n, m, W, T;
lint S[2005];
lint C[2005];
vector<ii> bruh;
lint points[2005];
lint bestmods[2005];

unordered_map<lint,lint> dp[2005];
lint nth[2005];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	fill(bestmods, bestmods+2001, 102345678901234LL);
	cin >> X >> m >> n >> W >> T;
	for(int i = 1;i <= m;i++){
		cin >> points[i];
	}
	points[m+1] = X;
	
	for(int i = 1;i <= n;i++){
		cin >> S[i] >> C[i];
		bruh.push_back({S[i], C[i]});
	}
	sort(all(bruh));
	for(int i = 1;i <= n;i++){
		S[i] = bruh[i-1].first;
		C[i] = bruh[i-1].second;
	}
	
	for(int i = 1;i <= m+1;i++){
		lint a = points[i] % T, b = points[i] / T;
		a = lower_bound(S+1, S+n+1, a) - (S);
		a--;
		bestmods[a] = min(bestmods[a], b);
	}
	
	nth[n+1] = 0LL;
	for(int i = n;i >= 1;i--){
		lint besthere = nth[i+1];
		for(ii p : dp[i+1]){
			besthere = min(besthere, p.second);
			
			dp[i][p.first] = p.second + C[i] + p.first * W;
		}
		
		if(bestmods[i] != 102345678901234LL){
			dp[i][bestmods[i]] = besthere + C[i] + bestmods[i] * W;
		}
		
		lint cnt = X / T;
		if(X % T > S[i]) cnt++;
		nth[i] = besthere + W * cnt;
	}
	
	lint ans = nth[1];
	for(ii p : dp[1]) ans = min(ans, p.second);
	
	ans += W*(X/T+1);
	cout << ans;
}

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