oj.uz

Submission #683979

# Submission time Handle Problem Language Result Execution time Memory
683979 2023-01-19T20:48:53 Z ethening Semiexpress (JOI17_semiexpress) C++17
100 / 100
 13 ms 2512 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 13 ms 2500 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 288 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 8 ms 2512 KB Output is correct
30 Correct 5 ms 1492 KB Output is correct