Submission #409299

#	Time	Username	Problem	Language	Result	Execution time	Memory
409299		ngpin04	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	9 ms	372 KiB

semiexpress

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 3e3 + 5;

long long T;
long long t[N];

int pos[N];
int nxt[N];
int s[N];
int n,m,k,a,b,c;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> T;
	for (int i = 1; i <= m; i++) {
		cin >> s[i];
		s[i]--;	
	}
	s[m + 1] = n;
	k -= m;

	for (int i = 1; i <= m; i++) {
		t[i] = T - (long long) s[i] * b;
		if (t[i] < 0) {
			m = i - 1;
			break;
		}
		pos[i] = min(0LL + s[i + 1], s[i] + t[i] / a + 1);
		t[i] -= (long long) (pos[i] - s[i]) * c;
	}

	while (k --) {
		int add = 0;
		int id = 0;
		for (int i = 1; i <= m; i++) if (t[i] >= 0) {
			nxt[i] = min(0LL + s[i + 1], pos[i] + t[i] / a + 1);
			if (add < nxt[i] - pos[i]) {
				add = nxt[i] - pos[i];
				id = i;
			}
		}

		if (id == 0)
			break;

		t[id] -= (long long) (nxt[id] - pos[id]) * c;
		pos[id] = nxt[id];
	}

	int ans = -1;
	for (int i = 1; i <= m; i++) {
		// cerr << s[i] << " " << pos[i] << "\n";
		ans += pos[i] - s[i];
	}
	cout << ans;
	return 0;
}

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