Submission #1071927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1071927	2024-08-23T12:29:19 Z	NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	20 / 100	1010 ms	2097152 KB

trade

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15 + 15;

void maximize(long long& x, long long y) {
	x = max(x, y); 
}

inline void dfs(int i, int st, int ck, vector<bool>& used, vector<vector<vector<bool>>>& vis, vector<vector<vector<vector<array<int, 3>>>>>& path) {
	if (vis[i][st][ck] == true) {
		return;
	}
	vis[i][st][ck] = true;
	if (i == 0 && ck == 1) {
		used[0] = true; 
	}
	for (auto [pi, pst, pk] : path[i][st][ck]) {
		if (pk == ck - 1) {
			used[i] = true; 
		}
		dfs(pi, pst, pk, used, vis, path); 
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> c(n), s(n);
	for (int i = 0; i < n; ++i) {
	  cin >> c[i];
	}
	for (int i = 0; i < n; ++i) {
	  cin >> s[i];
	}
	vector<vector<vector<long long>>> dp(n, vector<vector<long long>> (3, vector<long long> (k + 1, -INF)));
	dp[0][0][0] = 0;
	dp[0][1][1] = s[0] - c[0];
	if (k == 1) {
		dp[0][2][1] = s[0] - c[0];
	}
	for (int i = 1; i < n; ++i) {
		for (int st = 0; st < 3; ++st) {
			if (st == 0) {
				maximize(dp[i][0][0], dp[i - 1][0][0]);
				maximize(dp[i][1][1], dp[i - 1][0][0] + s[i] - c[i]);
			} else if (st == 1) {
				for (int j = 1; j < k; ++j) {
					maximize(dp[i][1][j], dp[i - 1][1][j] - c[i]);
					maximize(dp[i][1][j], dp[i - 1][1][j - 1] + s[i] - c[i]);
				}
				maximize(dp[i][2][k], dp[i - 1][1][k - 1] + s[i] - c[i]);
			} else {
				maximize(dp[i][2][k], dp[i - 1][2][k]); 
			}
		}
	}
	vector<vector<vector<vector<array<int, 3>>>>> path(n, vector<vector<vector<array<int, 3>>>> (3, vector<vector<array<int, 3>>> (k + 1))); 
	for (int i = 1; i < n; ++i) {
		for (int st = 0; st < 3; ++st) {
			if (st == 0) {
				if (dp[i][0][0] == dp[i - 1][0][0]) {
					path[i][0][0].push_back({i - 1, 0, 0});
				}
				if (dp[i][1][1] == dp[i - 1][0][0] + s[i] - c[i]) {
					path[i][1][1].push_back({i - 1, 0, 0});
				}
			} else if (st == 1) {
				for (int j = 1; j < k; ++j) {
					if (dp[i][1][j] == dp[i - 1][1][j] - c[i]) {
						path[i][1][j].push_back({i - 1, 1, j});
					}
					if (dp[i][1][j] == dp[i - 1][1][j - 1] + s[i] - c[i]) {
						path[i][1][j].push_back({i - 1, 1, j - 1});
					}
				}
				if (dp[i][2][k] == dp[i - 1][1][k - 1] + s[i] - c[i]) {
					path[i][2][k].push_back({i - 1, 1, k - 1});
				}
			} else {
				if (dp[i][2][k] == dp[i - 1][2][k]) {
					path[i][2][k].push_back({i - 1, 2, k});
				}
			}
		}
	}
	vector<bool> used(n); 
	vector<vector<vector<bool>>> vis(n, vector<vector<bool>> (3, vector<bool> (k + 1)));
	dfs(n - 1, 2, k, used, vis, path);
	cout << dp[n - 1][2][k] << '\n';
	for (int i = 0; i < n; ++i) {
	  cout << used[i];
	}
	return 0; 
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	432 KB	Output is correct

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2984 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	1 ms	432 KB	Output is correct
7	Correct	1 ms	1628 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	2 ms	2140 KB	Output is correct
10	Correct	2 ms	1456 KB	Output is correct
11	Correct	1 ms	1372 KB	Output is correct

Subtask #2

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	2 ms	2984 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	1 ms	432 KB	Output is correct
7	Correct	1 ms	1628 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	2 ms	2140 KB	Output is correct
10	Correct	2 ms	1456 KB	Output is correct
11	Correct	1 ms	1372 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	3 ms	2908 KB	Output is correct
16	Correct	3 ms	4956 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1628 KB	Output is correct
19	Correct	3 ms	2704 KB	Output is correct
20	Correct	2 ms	2140 KB	Output is correct
21	Correct	1 ms	1372 KB	Output is correct
22	Correct	2 ms	1372 KB	Output is correct
23	Runtime error	947 ms	2097152 KB	Execution killed with signal 9
24	Halted	0 ms	0 KB	-

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	270 ms	231508 KB	Output is correct
3	Correct	291 ms	233552 KB	Output is correct
4	Correct	294 ms	233664 KB	Output is correct
5	Correct	296 ms	233424 KB	Output is correct
6	Correct	295 ms	233040 KB	Output is correct
7	Correct	292 ms	232784 KB	Output is correct
8	Correct	288 ms	233552 KB	Output is correct
9	Correct	260 ms	231996 KB	Output is correct
10	Correct	280 ms	232580 KB	Output is correct

Subtask #4

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	270 ms	231508 KB	Output is correct
3	Correct	291 ms	233552 KB	Output is correct
4	Correct	294 ms	233664 KB	Output is correct
5	Correct	296 ms	233424 KB	Output is correct
6	Correct	295 ms	233040 KB	Output is correct
7	Correct	292 ms	232784 KB	Output is correct
8	Correct	288 ms	233552 KB	Output is correct
9	Correct	260 ms	231996 KB	Output is correct
10	Correct	280 ms	232580 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	269 ms	231504 KB	Output is correct
13	Correct	321 ms	233552 KB	Output is correct
14	Correct	294 ms	233556 KB	Output is correct
15	Correct	307 ms	233532 KB	Output is correct
16	Correct	310 ms	233040 KB	Output is correct
17	Correct	296 ms	232768 KB	Output is correct
18	Correct	302 ms	233556 KB	Output is correct
19	Correct	262 ms	232012 KB	Output is correct
20	Correct	294 ms	232532 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	2 ms	2908 KB	Output is correct
24	Correct	3 ms	4956 KB	Output is correct
25	Correct	0 ms	604 KB	Output is correct
26	Correct	2 ms	1628 KB	Output is correct
27	Correct	3 ms	2652 KB	Output is correct
28	Correct	3 ms	2140 KB	Output is correct
29	Correct	1 ms	1372 KB	Output is correct
30	Correct	2 ms	1372 KB	Output is correct
31	Runtime error	1010 ms	2097152 KB	Execution killed with signal 9
32	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	432 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	2984 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	1 ms	432 KB	Output is correct
9	Correct	1 ms	1628 KB	Output is correct
10	Correct	3 ms	2652 KB	Output is correct
11	Correct	2 ms	2140 KB	Output is correct
12	Correct	2 ms	1456 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	3 ms	2908 KB	Output is correct
18	Correct	3 ms	4956 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	2 ms	1628 KB	Output is correct
21	Correct	3 ms	2704 KB	Output is correct
22	Correct	2 ms	2140 KB	Output is correct
23	Correct	1 ms	1372 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct
25	Runtime error	947 ms	2097152 KB	Execution killed with signal 9
26	Halted	0 ms	0 KB	-