oj.uz

Submission #33297

# Submission time Handle Problem Language Result Execution time Memory
33297 2017-10-23T09:28:24 Z minkank Semiexpress (JOI17_semiexpress) C++14
100 / 100
 16 ms 2108 KB 
#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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2108 KB Output is correct
2 Correct 0 ms 2108 KB Output is correct
3 Correct 0 ms 2108 KB Output is correct
4 Correct 0 ms 2108 KB Output is correct
5 Correct 0 ms 2108 KB Output is correct
6 Correct 0 ms 2108 KB Output is correct
7 Correct 0 ms 2108 KB Output is correct
8 Correct 0 ms 2108 KB Output is correct
9 Correct 0 ms 2108 KB Output is correct
10 Correct 0 ms 2108 KB Output is correct
11 Correct 0 ms 2108 KB Output is correct
12 Correct 0 ms 2108 KB Output is correct
13 Correct 0 ms 2108 KB Output is correct
14 Correct 0 ms 2108 KB Output is correct
15 Correct 0 ms 2108 KB Output is correct
16 Correct 0 ms 2108 KB Output is correct
17 Correct 0 ms 2108 KB Output is correct
18 Correct 0 ms 2108 KB Output is correct
19 Correct 0 ms 2108 KB Output is correct
20 Correct 0 ms 2108 KB Output is correct
21 Correct 0 ms 2108 KB Output is correct
22 Correct 0 ms 2108 KB Output is correct
23 Correct 16 ms 2108 KB Output is correct
24 Correct 0 ms 2108 KB Output is correct
25 Correct 0 ms 2108 KB Output is correct
26 Correct 0 ms 2108 KB Output is correct
27 Correct 0 ms 2108 KB Output is correct
28 Correct 0 ms 2108 KB Output is correct
29 Correct 3 ms 2108 KB Output is correct
30 Correct 3 ms 2108 KB Output is correct