Submission #409299

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409299	2021-05-20T14:10:57 Z	ngpin04	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	9 ms	372 KB

semiexpress

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 3e3 + 5;

long long T;
long long t[N];

int pos[N];
int nxt[N];
int s[N];
int n,m,k,a,b,c;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> T;
	for (int i = 1; i <= m; i++) {
		cin >> s[i];
		s[i]--;	
	}
	s[m + 1] = n;
	k -= m;

	for (int i = 1; i <= m; i++) {
		t[i] = T - (long long) s[i] * b;
		if (t[i] < 0) {
			m = i - 1;
			break;
		}
		pos[i] = min(0LL + s[i + 1], s[i] + t[i] / a + 1);
		t[i] -= (long long) (pos[i] - s[i]) * c;
	}

	while (k --) {
		int add = 0;
		int id = 0;
		for (int i = 1; i <= m; i++) if (t[i] >= 0) {
			nxt[i] = min(0LL + s[i + 1], pos[i] + t[i] / a + 1);
			if (add < nxt[i] - pos[i]) {
				add = nxt[i] - pos[i];
				id = i;
			}
		}

		if (id == 0)
			break;

		t[id] -= (long long) (nxt[id] - pos[id]) * c;
		pos[id] = nxt[id];
	}

	int ans = -1;
	for (int i = 1; i <= m; i++) {
		// cerr << s[i] << " " << pos[i] << "\n";
		ans += pos[i] - s[i];
	}
	cout << ans;
	return 0;
}

Subtask #1

18.0 / 18.0

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

Subtask #2

30.0 / 30.0

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

Subtask #3

52.0 / 52.0

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