Submission #409283

#	Time	Username	Problem	Language	Result	Execution time	Memory
409283		ngpin04	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	2 ms	332 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;

	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] = s[i] + t[i] / a + 1;
		pos[i] = min(pos[i], s[i + 1]);
		t[i] -= (long long) (pos[i] - s[i]) * c;
	}

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

	long long 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: 0 / 52