Submission #697093

#	Time	Username	Problem	Language	Result	Execution time	Memory
697093		amunduzbaev	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2054 ms	29460 KiB

coach

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int X, n, m, w, t; cin >> X >> n >> m >> w >> t;
	vector<int> s(n), d(m), c(m);
	vector<ar<int, 2>> a;
	for(int i=0;i<n;i++){
		cin >> s[i];
		a.push_back({s[i] % t, -s[i]});
	}
	for(int i=0;i<m;i++){
		cin >> d[i] >> c[i];
		a.push_back({d[i], c[i]});
	}
	a.push_back({X % t, -X});
	a.push_back({0, 0});
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	int sz = a.size();
	vector<int> pref(sz), cnt(sz), tot(sz);
	for(int i=1;i<sz;i++){
		pref[i] = pref[i-1], cnt[i] = cnt[i-1];
		if(a[i][1] > 0){
			tot[i] = X / t + (a[i][0] <= (X % t));
			pref[i] += a[i][1];
			cnt[i]++;
		}
	}
	
	vector<int> dp(sz);
	dp[0] = (X / t + 1) * w;
	for(int i=1;i<sz;i++){
		if(a[i][1] > 0){
			dp[i] = dp[i-1] + tot[i] * w;
			continue;
		}
		
		dp[i] = dp[i-1];
		int s = -a[i][1] / t;
		for(int j=0;j<i;j++){
			//~ cout<<j<<" "<<i<<" "<<dp[j]<<" "<<s * w * (cnt[i] - cnt[j])<<" "<<pref[i] - pref[j]<<"\n";
			dp[i] = min(dp[i], dp[j] + s * w * (cnt[i] - cnt[j]) + pref[i] - pref[j]);
		}
	}
	
	//~ for(int i=0;i<sz;i++){
		//~ cout<<dp[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][0]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][1]<<" ";
	//~ } cout<<"\n";
	
	cout<<dp[sz - 1]<<"\n";
}

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