Submission #87851

#	Time	Username	Problem	Language	Result	Execution time	Memory
87851		KCSC	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	19 ms	1248 KiB

semiexpress

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

const int DIM = 3005;

long long pos[DIM], cnt[DIM];

int main(void) {
#ifdef HOME
	freopen("semiexpress.in", "r", stdin);
	freopen("semiexpress.out", "w", stdout);
#endif
	long long n, m, k, a, b, c, t;
	cin >> n >> m >> k >> a >> b >> c >> t; k -= m;
	for (int i = 1; i <= m; ++i) {
		cin >> pos[i]; --pos[i];	
		if (t - pos[i] * b < 0) { cnt[i] = -1; }
		else { cnt[i] = (t - pos[i] * b) / a; } }
	cnt[m] = min(cnt[m], 0LL);
	for (int i = 1; i < m; ++i) {
		cnt[i] = min(cnt[i], pos[i + 1] - pos[i] - 1); }
	while (k--) {	
		long long vl = 0, ps = -1;
		for (int i = 1; i < m; ++i) {
			if (t - pos[i] * b - (cnt[i] + 1) * c < 0) {
				continue; }
			long long st = cnt[i] + 1, 
					  en = min(pos[i + 1] - pos[i] - 1, (t - pos[i] * b - st * c) / a + st); 
			if (vl < en - st + 1) {		
				vl = en - st + 1; ps = i; } }
		cnt[ps] += vl; }
	long long ans = -1;	
	for (int i = 1; i <= m; ++i) {
		ans += cnt[i] + 1; }
	cout << ans;  
	return 0; }

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52