Submission #683979

#	Time	Username	Problem	Language	Result	Execution time	Memory
683979		ethening	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	13 ms	2512 KiB

semiexpress

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int n, m, k;
	cin >> n >> m >> k;
	k = k - m;

	ll a, b, c;
	cin >> a >> b >> c;
	ll T;
	cin >> T;
	vector<ll> S(m + 1);
	for (int i = 0; i < m; i++) {
		cin >> S[i];
	}
	S[m] = n + 1;

	ll ans = 0;
	
	vector<int> incr;
	for (int i = 0; i < m; i++) {
		ll cur = S[i];
		ll time_to_exp = b * (cur - 1);
		if (time_to_exp > T) break;
		ll lst = max((T - time_to_exp), 0ll) / a + cur;
		// cout << "**" << lst << endl;
		lst = min(lst, S[i + 1] - 1);
		// cout << i << " " << 0 << " " << cur << " " << lst << endl;
		ans += (lst - cur + 1);
		cur = lst + 1;
		for (int j = 1; j <= k; j++) {
			if (cur >= S[i + 1]) break;
			ll time_to_semiexp = c * (cur - S[i]);
			if (time_to_exp + time_to_semiexp > T) break;
			// cout << "##" << time_to_exp + time_to_semiexp << endl;
			lst = max((T - (time_to_exp + time_to_semiexp)), 0ll) / a + cur;
			// cout << "^" << lst << endl;
			lst = min(lst, S[i + 1] - 1);
			// cout << i << " " << j << " " << cur << " " << lst << endl;
			incr.push_back(lst - cur + 1);
			cur = lst + 1;
		}
	}
	
	sort(incr.begin(), incr.end(), greater<int>());
	int sz = (int)incr.size();
	for (int i = 0; i < min(k, sz); i++) {
		ans += incr[i];
	}
	
	cout << ans - 1 << endl;
	// for (int i = 0; i < m; i++) {
	// 	for (int j = 0; j <= k; j++) {
	// 		cout << i << " " << j << " " << dp[i][j] << endl;
	// 	}
	// }
	
	// dp2[i] = dp[j] + dp2[i - j]
}

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