Submission #409285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409285	2021-05-20T13:58:34 Z	ngpin04	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	2 ms	332 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];
long long pos[N];
long long nxt[N];
long long 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;

	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] = s[i] + t[i] / a + 1;
		pos[i] = min(pos[i], s[i + 1]);
		t[i] -= (long long) (pos[i] - s[i]) * c;
	}

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

	long long 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	332 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	332 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	332 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	332 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	332 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	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 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	332 KB	Output is correct

Subtask #3

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 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	332 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	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 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	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Incorrect	2 ms	332 KB	Output isn't correct
22	Halted	0 ms	0 KB	-