oj.uz

Submission #1072187

# Submission time Handle Problem Language Result Execution time Memory
1072187 2024-08-23T15:18:30 Z NeroZein Tricks of the Trade (CEOI23_trade) C++17
55 / 100
 3134 ms 2097152 KB 
#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<bool>>> vis(n, vector<vector<bool>> (3, vector<bool> (k + 1)));
	vector<vector<vector<long long>>> dp(n, vector<vector<long long>> (3, vector<long long> (k + 1)));
	function<long long(int, int, int)> bt = [&](int i, int st, int ck) {
		if (ck > k) {
			return -INF;
		}
		if (i == n) {
			return (st == 2 && ck == k ? 0 : -INF);
		}
		long long& ret = dp[i][st][ck];
		if (vis[i][st][ck]) {
			return ret;
		}
		vis[i][st][ck] = true; 
		ret = -INF;
		if (st == 0) {
			ret = bt(i + 1, 0, 0);
			if (k == 1) {
				ret = max(ret, bt(i + 1, 2, 1) + s[i] - c[i]);
			} else {
				ret = max(ret, bt(i + 1, 1, 1) + s[i] - c[i]);				
			}
		} else if (st == 1) {
			ret = bt(i + 1, 1, ck) - c[i];
			if (ck + 1 < k) {
				ret = max(ret, bt(i + 1, 1, ck + 1) + s[i] - c[i]);				
			} else {
				ret = max(ret, bt(i + 1, 2, ck + 1) + s[i] - c[i]); 
			}
		} else {
			ret = bt(i + 1, 2, ck); 
		}
		return ret; 
	};
	vector<int> used(n); 
	vector<vector<vector<bool>>> vis2(n, vector<vector<bool>> (3, vector<bool> (k + 1)));
	function<void(int, int, int)> path = [&](int i, int st, int ck) {
		if (i == n) {
			return;
		}
		if (vis2[i][st][ck] == true) {
			return;
		}
		vis2[i][st][ck] = true;
		long long ret = dp[i][st][ck];
		if (st == 0) {
			if (ret == bt(i + 1, 0, 0)) {
				path(i + 1, 0, 0);
			}
			if (k == 1 && ret == bt(i + 1, 2, 1) + s[i] - c[i]) {
				path(i + 1, 2, 1);
				used[i] = 1;
			}
			if (k > 1 && ret == bt(i + 1, 1, 1) + s[i] - c[i]) {
				used[i] = 1; 
				path(i + 1, 1, 1);
			} 
		} else if (st == 1) {
			if (ret == bt(i + 1, 1, ck) - c[i]) {
				path(i + 1, 1, ck);
			}
			if (ck + 1 < k && ret == bt(i + 1, 1, ck + 1) + s[i] - c[i]) {
				used[i] = 1; 
				path(i + 1, 1, ck + 1);
			} 
			if (ck + 1 == k && ret == bt(i + 1, 2, ck + 1) + s[i] - c[i]) {
				used[i] = 1;
				path(i + 1, 2, ck + 1);
			}
		} else {
			path(i + 1, 2, ck); 
		}
	};
	cout << bt(0, 0, 0) << '\n';
	path(0, 0, 0);
	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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 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 1 ms 860 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 640 KB Output is correct

Subtask #2
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 1 ms 860 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 0 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 1 ms 860 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 688 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 951 ms 876884 KB Output is correct
24 Correct 7 ms 6236 KB Output is correct
25 Correct 248 ms 150304 KB Output is correct
26 Correct 42 ms 19544 KB Output is correct
27 Correct 928 ms 379024 KB Output is correct
28 Correct 6 ms 5724 KB Output is correct
29 Correct 548 ms 440548 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 276 ms 229520 KB Output is correct
3 Correct 286 ms 231512 KB Output is correct
4 Correct 290 ms 231760 KB Output is correct
5 Correct 314 ms 231628 KB Output is correct
6 Correct 299 ms 231248 KB Output is correct
7 Correct 296 ms 230788 KB Output is correct
8 Correct 293 ms 231508 KB Output is correct
9 Correct 255 ms 229972 KB Output is correct
10 Correct 319 ms 230740 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 276 ms 229520 KB Output is correct
3 Correct 286 ms 231512 KB Output is correct
4 Correct 290 ms 231760 KB Output is correct
5 Correct 314 ms 231628 KB Output is correct
6 Correct 299 ms 231248 KB Output is correct
7 Correct 296 ms 230788 KB Output is correct
8 Correct 293 ms 231508 KB Output is correct
9 Correct 255 ms 229972 KB Output is correct
10 Correct 319 ms 230740 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 254 ms 229456 KB Output is correct
13 Correct 280 ms 231612 KB Output is correct
14 Correct 275 ms 231764 KB Output is correct
15 Correct 333 ms 231600 KB Output is correct
16 Correct 291 ms 231244 KB Output is correct
17 Correct 285 ms 230608 KB Output is correct
18 Correct 278 ms 231508 KB Output is correct
19 Correct 256 ms 229972 KB Output is correct
20 Correct 300 ms 230740 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1937 ms 1417664 KB Output is correct
32 Correct 348 ms 243284 KB Output is correct
33 Correct 3134 ms 1417156 KB Output is correct
34 Correct 2685 ms 1416904 KB Output is correct
35 Correct 2158 ms 1416784 KB Output is correct
36 Correct 2861 ms 1415756 KB Output is correct
37 Correct 2960 ms 1415492 KB Output is correct

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 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 1 ms 860 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 0 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 1 ms 860 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 688 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 951 ms 876884 KB Output is correct
26 Correct 7 ms 6236 KB Output is correct
27 Correct 248 ms 150304 KB Output is correct
28 Correct 42 ms 19544 KB Output is correct
29 Correct 928 ms 379024 KB Output is correct
30 Correct 6 ms 5724 KB Output is correct
31 Correct 548 ms 440548 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 276 ms 229520 KB Output is correct
34 Correct 286 ms 231512 KB Output is correct
35 Correct 290 ms 231760 KB Output is correct
36 Correct 314 ms 231628 KB Output is correct
37 Correct 299 ms 231248 KB Output is correct
38 Correct 296 ms 230788 KB Output is correct
39 Correct 293 ms 231508 KB Output is correct
40 Correct 255 ms 229972 KB Output is correct
41 Correct 319 ms 230740 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 254 ms 229456 KB Output is correct
44 Correct 280 ms 231612 KB Output is correct
45 Correct 275 ms 231764 KB Output is correct
46 Correct 333 ms 231600 KB Output is correct
47 Correct 291 ms 231244 KB Output is correct
48 Correct 285 ms 230608 KB Output is correct
49 Correct 278 ms 231508 KB Output is correct
50 Correct 256 ms 229972 KB Output is correct
51 Correct 300 ms 230740 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 344 KB Output is correct
54 Correct 1 ms 860 KB Output is correct
55 Correct 2 ms 1372 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 600 KB Output is correct
58 Correct 1 ms 860 KB Output is correct
59 Correct 1 ms 860 KB Output is correct
60 Correct 1 ms 604 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 1937 ms 1417664 KB Output is correct
63 Correct 348 ms 243284 KB Output is correct
64 Correct 3134 ms 1417156 KB Output is correct
65 Correct 2685 ms 1416904 KB Output is correct
66 Correct 2158 ms 1416784 KB Output is correct
67 Correct 2861 ms 1415756 KB Output is correct
68 Correct 2960 ms 1415492 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 260 ms 229412 KB Output is correct
71 Correct 288 ms 231764 KB Output is correct
72 Correct 276 ms 231764 KB Output is correct
73 Correct 300 ms 231364 KB Output is correct
74 Correct 315 ms 231264 KB Output is correct
75 Correct 294 ms 230740 KB Output is correct
76 Correct 303 ms 231504 KB Output is correct
77 Correct 253 ms 229964 KB Output is correct
78 Correct 299 ms 230720 KB Output is correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 1 ms 860 KB Output is correct
82 Correct 1 ms 1372 KB Output is correct
83 Correct 0 ms 604 KB Output is correct
84 Correct 1 ms 604 KB Output is correct
85 Correct 2 ms 860 KB Output is correct
86 Correct 1 ms 860 KB Output is correct
87 Correct 1 ms 604 KB Output is correct
88 Correct 1 ms 604 KB Output is correct
89 Correct 1794 ms 1417556 KB Output is correct
90 Correct 325 ms 243280 KB Output is correct
91 Correct 2877 ms 1417044 KB Output is correct
92 Correct 2594 ms 1416784 KB Output is correct
93 Correct 1918 ms 1416788 KB Output is correct
94 Correct 2728 ms 1416000 KB Output is correct
95 Correct 3033 ms 1415508 KB Output is correct
96 Correct 933 ms 876968 KB Output is correct
97 Correct 8 ms 6236 KB Output is correct
98 Correct 244 ms 150428 KB Output is correct
99 Correct 37 ms 19580 KB Output is correct
100 Correct 916 ms 378964 KB Output is correct
101 Correct 7 ms 5724 KB Output is correct
102 Correct 570 ms 440628 KB Output is correct
103 Runtime error 961 ms 2097152 KB Execution killed with signal 9
104 Halted 0 ms 0 KB -