Submission #765515

#	Time	Username	Problem	Language	Result	Execution time	Memory
765515		NK_	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	2 ms	468 KiB

semiexpress

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, M, K; cin >> N >> M >> K;
	ll A, B, C; cin >> A >> B >> C;

	ll T; cin >> T;

	V<int> S(M); for(auto& x : S) cin >> x;
	S.pb(N + 1);

	K -= M;

	set<array<ll, 5>> opt;

	int ans = 0;

	for(int i = 0; i < M; i++) {
		int L = S[i], R = S[i+1];
		ll t = (S[i] - 1) * 1LL * B;

		// t + kA <= T
		// kA <= T - t;
		if (T >= t) {
			ll k = (T - t) / A;
			int l = min(L + k + 1, R + 0LL);
			// cout << t << " " << k << " " << L << " " << l << " " << R << endl;
			ans += l - L;

			ll tl = t + (l - L) * C;
			if (T >= tl) {
				// cout << tl << endl;
				ll k_ = (T - tl) / A;
				int can = min(l + k_ + 1, R + 0LL);
				// cout << k_ << " " << can << endl;
				if (can > l) opt.insert({can - l, tl, l, L, R});
			}
		}
	}

	// cout << endl;

	while(K--) { 
		if (sz(opt) == 0) break;
		auto [add, t, l, L, R] = *rbegin(opt); opt.erase(prev(end(opt)));

		// cout << add << " " << t << " " << l << " " << L << " " << R << endl;

		ans += add;
		l += add;

		ll tl = t + add * C;
		// c << tl << endl;
		if (T >= tl) {
			ll k_ = (T - tl) / A;
			int can = min(l + k_ + 1, R + 0LL);
			// cout << k_ << " " << can << endl;
			if (can > l) opt.insert({can - l, tl, l, L, R});
		}
	}

	cout << ans - 1 << nl;
    return 0;
}

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