Submission #33297

#	Time	Username	Problem	Language	Result	Execution time	Memory
33297		minkank	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	16 ms	2108 KiB

semiexpress

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

#define int long long

const int N = 3005;

int n, m, k, t, l[N], r[N], a, b, c, ans, val[N], ti[N];

signed main() {
	cin >> n >> m >> k >> a >> b >> c >> t;
	for(int i = 1; i <= m; ++i) {
		cin >> l[i];
		if(b * (l[i] - 1) > t) l[i] = 0;
	}
	for(int i = 1; i <= m; ++i) if(l[i]) {
		r[i] = min(n, l[i] + (t - b * (l[i] - 1)) / a);
		if(l[i + 1]) r[i] = min(r[i], l[i + 1] - 1);
		val[i] = l[i];
		ti[i] = (l[i] - 1) * b;
		ans += max(0LL, (r[i] - l[i] + 1));
	}
	for(int i = 1; i <= k - m; ++i) {
		int pos = 0, cur = 0;
		for(int j = 1; j <= m; ++j) if(l[j]) {
			int VAL = r[j] + 1, TI = ti[j] + (VAL - val[j]) * c;
			if(TI > t) continue;
			int R = min(n, VAL + (t - TI) / a); if(l[j + 1]) R = min(R, l[j + 1] - 1);
			if(cur < R - VAL + 1) { cur = R - VAL + 1; pos = j; }
		}
		if(pos == 0) break;
		int VAL = r[pos] + 1, TI = ti[pos] + (VAL - val[pos]) * c;
		int R = min(n, VAL + (t - TI) / a); if(l[pos + 1]) R = min(R, l[pos + 1] - 1);
		val[pos] = VAL; ti[pos] = TI; r[pos] = R;
		ans += cur;
	}
	cout << ans - 1;
}

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