Submission #1234694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234694		PenguinsAreCute	Long Distance Coach (JOI17_coach)	C++17	16 / 100	2 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], d[m], c[m];
	for(int i=0;i<n;i++)
		cin >> s[i];
	s[n++] = x;
	for(int i=0;i<m;i++)
		cin >> d[i] >> c[i];
	long long ans = 0;
	for(int i=0;i<(1<<m);i++) {
		long long eject[m];
		memset(eject,1,sizeof(eject));
		for(int j=0;j<n;j++)
			for(int k=0;k<m;k++)
				if((i&(1<<k)) && d[k] < (s[j] % t)) {
					bool ok = 1;
					for(int l=0;l<m;l++)
						if((s[j] % t) > d[l] && d[l] > d[k] && !(i & (1 << l)))
							ok = 0;
					if(ok)
						eject[k] = min(eject[k], s[j] - (s[j] % t) + d[k]);
				}
		long long cur = 0;
		for(int j=0;j<m;j++)
			if(i&(1<<j))
				cur += (eject[j] > 1e13 ? 1e17 : c[j] - w * ((x - eject[j]) / t + 1));
		ans = min(ans, cur);
	}
	ans += w * ((x / t) + 1);
	for(int i=0;i<m;i++)
		ans += w * ((x - d[i]) / t + 1);
	cout << ans;
}

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