Submission #1234707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234707		PenguinsAreCute	Long Distance Coach (JOI17_coach)	C++17	0 / 100	0 ms	328 KiB

coach

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long x, t, w;
	int n, m;
	cin >> x >> n >> m >> w >> t;
	long long s[n+1];
	for(int i=0;i<n;i++)
		cin >> s[i];
	s[n++] = x;
	pair<long long, long long> ppl[m];
	for(int i=0;i<m;i++)
		cin >> ppl[i].first >> ppl[i].second;
	long long d[m], c[m];
	for(int i=0;i<m;i++)
		d[i] = ppl[i].first, c[i] = ppl[i].second;
	sort(s,s+n);
	sort(ppl,ppl+m);
	long long dp[m+1][m+1];
	memset(dp,1,sizeof(dp));
	dp[m][m] = 0;
	for(int i=m;i;i--)
		for(int j=i;j<m+1;j++) {
			dp[i-1][i-1] = min(dp[i-1][i-1],dp[i][j]);
			long long minT = 1e18;
			for(int k=0;k<n;k++)
				if((s[k] % t) > d[i-1] && (j == m || (s[k] % t) < d[j]))
					minT = min(minT, s[k]);
			minT -= (minT % t);
			minT += d[i-1];
			if(minT < 1e18)
				dp[i-1][j] = dp[i][j] + c[i-1] - (x - minT) / t * w - w;
		}
	long long ans = *min_element(dp[0],dp[0]+m+1);
	ans += w * ((x / t) + 1);
	for(int i=0;i<m;i++)
		ans += w * ((x - d[i]) / t + 1);
	cout << ans;
}

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