Submission #1234902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234902		emptypringlescan	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2096 ms	9800 KiB

coach

#include <bits/stdc++.h>
using namespace std;
long long x;
int n,m;
long long w,t;
bool cmp(long long a, long long b){
	if(a%t!=b%t) return a%t<b%t;
	else return a<b;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> x >> n >> m >> w >> t;
	n++;
	long long arr[n];
	for(int i=0; i<n-1; i++) cin >> arr[i];
	arr[n-1]=x;
	sort(arr,arr+n,cmp);
	pair<long long,long long> brr[m];
	long long pref[m+1];
	pref[0]=0;
	for(int i=0; i<m; i++) cin >> brr[i].first >> brr[i].second;
	sort(brr,brr+m);
	for(int i=1; i<=m; i++) pref[i]=pref[i-1]+brr[i-1].second;
	long long ans=(x/t+1)*w;
	long long rem=x%t;
	long long save[m+1];
	save[0]=0;
	for(int i=0; i<m; i++){
		if(brr[i].first<rem){
			ans+=w*(x/t+1);
			save[i+1]=save[i]+x/t+1;
		}
		else{
			ans+=x/t*w;
			save[i+1]=save[i]+x/t;
		}
	}
	//cout << ans << '\n';
	int cnt=0;
	long long dp[m+5];
	for(int i=0; i<=m; i++) dp[i]=1e16;
	dp[0]=0;
	for(int i=1; i<=m; i++){
		dp[i]=dp[i-1];
		while(cnt<n&&(i==m||arr[cnt]%t<brr[i].first)){
			if(arr[cnt]%t<brr[i-1].first){
				cnt++;
				continue;
			}
			for(int j=i-1; j>=0; j--){
				long long nv=dp[j]-(pref[i]-pref[j]);
				nv+=w*(save[i]-save[j]-(arr[cnt]/t)*(long long)(i-j));
				dp[i]=max(dp[i],nv);
				//cout << save[i]-save[j] << ' ' << (arr[cnt]/t) << ' ' << pref[i]-pref[j] << '\n';
			//	cout << j << ' ' << nv << '\n';
			}
			cnt++;
		}
		//cout << dp[i] << '\n';
	}
	cout << ans-dp[m];
}

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