oj.uz

답안 #559469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559469 2022-05-09T23:36:49 Z AlperenT Jelly Flavours (IOI20_jelly) C++17
33 / 100
 180 ms 152688 KB 
#include "jelly.h"
#include <bits/stdc++.h>

const int INF = 1e9 + 5;

using namespace std;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){
	int n = a.size(), ans = 0;

	vector arr(n, pair{0, 0});

	for(int i = 0; i < n; i++) arr[i] = {a[i], b[i]};

	sort(arr.begin(), arr.end());

	vector dp1(n, vector(x + 1, INF));
	vector dp2(n, vector(y + 1, 0));

	dp1[0][0] = arr[0].second;
	dp1[0][arr[0].first] = 0;

	for(int i = 1; i < n; i++){
		for(int j = 0; j <= x; j++){
			dp1[i][j] = min(dp1[i][j], dp1[i - 1][j] + arr[i].second);
			if(j >= arr[i].first) dp1[i][j] = min(dp1[i][j], dp1[i - 1][j - arr[i].first]);
		}
	}

	dp2[n - 1][arr[n - 1].second] = 1;

	for(int i = n - 2; i >= 0; i--){
		for(int j = 0; j <= y; j++){
			dp2[i][j] = dp2[i + 1][j];
			if(j - arr[i].second >= 0) dp2[i][j] = max(dp2[i][j], dp2[i + 1][j - arr[i].second] + 1);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= x; j++){
			if(dp1[i][j] <= y){
				ans = max(ans, (i + 1) + (i + 1 < n ? dp2[i + 1][y - dp1[i][j]] : 0));
			}
		}
	}

	return ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 13396 KB Output is correct
2 Correct 20 ms 20664 KB Output is correct
3 Correct 6 ms 5716 KB Output is correct
4 Correct 10 ms 8404 KB Output is correct
5 Correct 57 ms 53716 KB Output is correct
6 Correct 65 ms 68188 KB Output is correct
7 Correct 66 ms 65968 KB Output is correct
8 Correct 13 ms 13012 KB Output is correct
9 Correct 73 ms 69972 KB Output is correct
10 Correct 34 ms 28884 KB Output is correct
11 Correct 69 ms 61468 KB Output is correct
12 Correct 49 ms 48440 KB Output is correct
13 Correct 40 ms 42324 KB Output is correct
14 Correct 16 ms 13652 KB Output is correct
15 Correct 52 ms 48840 KB Output is correct
16 Correct 47 ms 46508 KB Output is correct
17 Correct 48 ms 49176 KB Output is correct
18 Correct 53 ms 52720 KB Output is correct
19 Correct 49 ms 41684 KB Output is correct
20 Correct 14 ms 13524 KB Output is correct
21 Correct 15 ms 13396 KB Output is correct
22 Correct 27 ms 20792 KB Output is correct
23 Correct 6 ms 5716 KB Output is correct
24 Correct 13 ms 8436 KB Output is correct
25 Correct 63 ms 53840 KB Output is correct
26 Correct 67 ms 68160 KB Output is correct
27 Correct 64 ms 66036 KB Output is correct
28 Correct 13 ms 13012 KB Output is correct
29 Correct 72 ms 69972 KB Output is correct
30 Correct 30 ms 28848 KB Output is correct
31 Correct 61 ms 61440 KB Output is correct
32 Correct 48 ms 48500 KB Output is correct
33 Correct 50 ms 42348 KB Output is correct
34 Correct 22 ms 13744 KB Output is correct
35 Correct 57 ms 48816 KB Output is correct
36 Correct 48 ms 46504 KB Output is correct
37 Correct 54 ms 49108 KB Output is correct
38 Correct 53 ms 52792 KB Output is correct
39 Correct 46 ms 41684 KB Output is correct
40 Correct 15 ms 13524 KB Output is correct
41 Correct 15 ms 13396 KB Output is correct
42 Correct 23 ms 20692 KB Output is correct
43 Correct 7 ms 5716 KB Output is correct
44 Correct 14 ms 8372 KB Output is correct
45 Correct 55 ms 53752 KB Output is correct
46 Correct 65 ms 68140 KB Output is correct
47 Correct 63 ms 65964 KB Output is correct
48 Correct 12 ms 13124 KB Output is correct
49 Correct 78 ms 70064 KB Output is correct
50 Correct 35 ms 28908 KB Output is correct
51 Correct 71 ms 61524 KB Output is correct
52 Correct 47 ms 48484 KB Output is correct
53 Correct 41 ms 42256 KB Output is correct
54 Correct 15 ms 13644 KB Output is correct
55 Correct 57 ms 48824 KB Output is correct
56 Correct 48 ms 46420 KB Output is correct
57 Correct 67 ms 49200 KB Output is correct
58 Correct 53 ms 52824 KB Output is correct
59 Correct 43 ms 41740 KB Output is correct
60 Correct 14 ms 13524 KB Output is correct
61 Correct 14 ms 13472 KB Output is correct
62 Correct 21 ms 20772 KB Output is correct
63 Correct 6 ms 5716 KB Output is correct
64 Correct 13 ms 8404 KB Output is correct
65 Correct 81 ms 53768 KB Output is correct
66 Correct 98 ms 68172 KB Output is correct
67 Correct 64 ms 65988 KB Output is correct
68 Correct 13 ms 13012 KB Output is correct
69 Correct 76 ms 70060 KB Output is correct
70 Correct 31 ms 28884 KB Output is correct
71 Correct 64 ms 61428 KB Output is correct
72 Correct 51 ms 48504 KB Output is correct
73 Correct 44 ms 42328 KB Output is correct
74 Correct 17 ms 13652 KB Output is correct
75 Correct 61 ms 48836 KB Output is correct
76 Correct 48 ms 46380 KB Output is correct
77 Correct 50 ms 49100 KB Output is correct
78 Correct 65 ms 52832 KB Output is correct
79 Correct 47 ms 41652 KB Output is correct
80 Correct 16 ms 13524 KB Output is correct
81 Correct 15 ms 13504 KB Output is correct
82 Correct 22 ms 20692 KB Output is correct
83 Correct 6 ms 5716 KB Output is correct
84 Correct 10 ms 8432 KB Output is correct
85 Correct 63 ms 53708 KB Output is correct
86 Correct 67 ms 68180 KB Output is correct
87 Correct 65 ms 65924 KB Output is correct
88 Correct 14 ms 13128 KB Output is correct
89 Correct 80 ms 70016 KB Output is correct
90 Correct 33 ms 28788 KB Output is correct
91 Correct 60 ms 61504 KB Output is correct
92 Correct 64 ms 48432 KB Output is correct
93 Correct 43 ms 42356 KB Output is correct
94 Correct 15 ms 13652 KB Output is correct
95 Correct 53 ms 48820 KB Output is correct
96 Correct 48 ms 46500 KB Output is correct
97 Correct 54 ms 49100 KB Output is correct
98 Correct 54 ms 52780 KB Output is correct
99 Correct 43 ms 41752 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 81696 KB Output is correct
2 Correct 133 ms 146700 KB Output is correct
3 Correct 136 ms 145028 KB Output is correct
4 Correct 143 ms 148408 KB Output is correct
5 Correct 147 ms 152648 KB Output is correct
6 Correct 133 ms 144460 KB Output is correct
7 Correct 138 ms 145268 KB Output is correct
8 Correct 126 ms 147688 KB Output is correct
9 Correct 138 ms 142120 KB Output is correct
10 Correct 159 ms 146608 KB Output is correct
11 Correct 63 ms 79052 KB Output is correct
12 Correct 1 ms 428 KB Output is correct
13 Correct 58 ms 73812 KB Output is correct
14 Correct 59 ms 75672 KB Output is correct
15 Correct 63 ms 77584 KB Output is correct
16 Correct 56 ms 72812 KB Output is correct
17 Correct 73 ms 73132 KB Output is correct
18 Correct 96 ms 82832 KB Output is correct
19 Correct 99 ms 82792 KB Output is correct
20 Correct 81 ms 70852 KB Output is correct
21 Correct 86 ms 81732 KB Output is correct
22 Correct 126 ms 146588 KB Output is correct
23 Correct 126 ms 144984 KB Output is correct
24 Correct 146 ms 148312 KB Output is correct
25 Correct 168 ms 152660 KB Output is correct
26 Correct 158 ms 144436 KB Output is correct
27 Correct 132 ms 145316 KB Output is correct
28 Correct 127 ms 147716 KB Output is correct
29 Correct 162 ms 142108 KB Output is correct
30 Correct 142 ms 146632 KB Output is correct
31 Correct 60 ms 79148 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 68 ms 73804 KB Output is correct
34 Correct 78 ms 75672 KB Output is correct
35 Correct 80 ms 77612 KB Output is correct
36 Correct 53 ms 72780 KB Output is correct
37 Correct 74 ms 73020 KB Output is correct
38 Correct 102 ms 82832 KB Output is correct
39 Correct 98 ms 82688 KB Output is correct
40 Correct 79 ms 70848 KB Output is correct
41 Correct 87 ms 81616 KB Output is correct
42 Correct 127 ms 146636 KB Output is correct
43 Correct 133 ms 144944 KB Output is correct
44 Correct 155 ms 148288 KB Output is correct
45 Correct 139 ms 152688 KB Output is correct
46 Correct 141 ms 144476 KB Output is correct
47 Correct 139 ms 145200 KB Output is correct
48 Correct 125 ms 147800 KB Output is correct
49 Correct 168 ms 142104 KB Output is correct
50 Correct 164 ms 146712 KB Output is correct
51 Correct 60 ms 79180 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 57 ms 73804 KB Output is correct
54 Correct 65 ms 75604 KB Output is correct
55 Correct 63 ms 77692 KB Output is correct
56 Correct 56 ms 72780 KB Output is correct
57 Correct 77 ms 73156 KB Output is correct
58 Correct 77 ms 82896 KB Output is correct
59 Correct 93 ms 82768 KB Output is correct
60 Correct 82 ms 70852 KB Output is correct
61 Correct 95 ms 81728 KB Output is correct
62 Correct 134 ms 146780 KB Output is correct
63 Correct 139 ms 144948 KB Output is correct
64 Correct 138 ms 148288 KB Output is correct
65 Correct 149 ms 152684 KB Output is correct
66 Correct 136 ms 144564 KB Output is correct
67 Correct 131 ms 145308 KB Output is correct
68 Correct 131 ms 147676 KB Output is correct
69 Correct 143 ms 142068 KB Output is correct
70 Correct 148 ms 146584 KB Output is correct
71 Correct 57 ms 79128 KB Output is correct
72 Correct 1 ms 428 KB Output is correct
73 Correct 58 ms 73736 KB Output is correct
74 Correct 62 ms 75596 KB Output is correct
75 Correct 76 ms 77608 KB Output is correct
76 Correct 61 ms 72784 KB Output is correct
77 Correct 82 ms 73172 KB Output is correct
78 Correct 81 ms 82836 KB Output is correct
79 Correct 87 ms 82796 KB Output is correct
80 Correct 88 ms 70848 KB Output is correct
81 Correct 81 ms 81736 KB Output is correct
82 Correct 131 ms 146700 KB Output is correct
83 Correct 124 ms 144940 KB Output is correct
84 Correct 149 ms 148480 KB Output is correct
85 Correct 164 ms 152576 KB Output is correct
86 Correct 124 ms 144480 KB Output is correct
87 Correct 126 ms 145280 KB Output is correct
88 Correct 125 ms 147788 KB Output is correct
89 Correct 155 ms 142124 KB Output is correct
90 Correct 148 ms 146508 KB Output is correct
91 Correct 64 ms 79140 KB Output is correct
92 Correct 1 ms 468 KB Output is correct
93 Correct 69 ms 73896 KB Output is correct
94 Correct 63 ms 75604 KB Output is correct
95 Correct 66 ms 77644 KB Output is correct
96 Correct 58 ms 72908 KB Output is correct
97 Correct 71 ms 73152 KB Output is correct
98 Correct 92 ms 82764 KB Output is correct
99 Correct 105 ms 82816 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 79420 KB Output is correct
2 Correct 135 ms 141440 KB Output is correct
3 Correct 134 ms 140384 KB Output is correct
4 Correct 155 ms 148028 KB Output is correct
5 Correct 143 ms 143852 KB Output is correct
6 Correct 138 ms 145796 KB Output is correct
7 Correct 139 ms 147108 KB Output is correct
8 Correct 125 ms 143544 KB Output is correct
9 Correct 134 ms 142380 KB Output is correct
10 Correct 144 ms 152284 KB Output is correct
11 Correct 58 ms 74360 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 96 ms 88136 KB Output is correct
14 Correct 72 ms 78144 KB Output is correct
15 Correct 71 ms 84704 KB Output is correct
16 Correct 63 ms 78272 KB Output is correct
17 Correct 82 ms 85728 KB Output is correct
18 Correct 85 ms 85324 KB Output is correct
19 Correct 92 ms 76236 KB Output is correct
20 Correct 83 ms 77344 KB Output is correct
21 Correct 78 ms 79504 KB Output is correct
22 Correct 123 ms 141456 KB Output is correct
23 Correct 120 ms 140508 KB Output is correct
24 Correct 178 ms 147976 KB Output is correct
25 Correct 148 ms 143820 KB Output is correct
26 Correct 136 ms 145796 KB Output is correct
27 Correct 127 ms 147108 KB Output is correct
28 Correct 138 ms 143628 KB Output is correct
29 Correct 148 ms 142436 KB Output is correct
30 Correct 157 ms 152288 KB Output is correct
31 Correct 67 ms 74484 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 74 ms 88136 KB Output is correct
34 Correct 66 ms 78268 KB Output is correct
35 Correct 75 ms 84688 KB Output is correct
36 Correct 75 ms 78268 KB Output is correct
37 Correct 90 ms 85760 KB Output is correct
38 Correct 86 ms 85340 KB Output is correct
39 Correct 79 ms 76260 KB Output is correct
40 Correct 84 ms 77348 KB Output is correct
41 Correct 89 ms 79508 KB Output is correct
42 Correct 118 ms 141352 KB Output is correct
43 Correct 122 ms 140504 KB Output is correct
44 Correct 135 ms 147924 KB Output is correct
45 Correct 145 ms 143820 KB Output is correct
46 Correct 132 ms 145768 KB Output is correct
47 Correct 124 ms 147112 KB Output is correct
48 Correct 122 ms 143552 KB Output is correct
49 Correct 153 ms 142444 KB Output is correct
50 Correct 154 ms 152316 KB Output is correct
51 Correct 59 ms 74416 KB Output is correct
52 Correct 2 ms 468 KB Output is correct
53 Correct 75 ms 88136 KB Output is correct
54 Correct 64 ms 78268 KB Output is correct
55 Correct 85 ms 84616 KB Output is correct
56 Correct 70 ms 78156 KB Output is correct
57 Correct 94 ms 85884 KB Output is correct
58 Correct 86 ms 85316 KB Output is correct
59 Correct 86 ms 76196 KB Output is correct
60 Correct 98 ms 77228 KB Output is correct
61 Correct 81 ms 79472 KB Output is correct
62 Correct 129 ms 141376 KB Output is correct
63 Correct 122 ms 140496 KB Output is correct
64 Correct 151 ms 147908 KB Output is correct
65 Correct 143 ms 143868 KB Output is correct
66 Correct 133 ms 145804 KB Output is correct
67 Correct 123 ms 147224 KB Output is correct
68 Correct 128 ms 143564 KB Output is correct
69 Correct 150 ms 142544 KB Output is correct
70 Correct 155 ms 152332 KB Output is correct
71 Correct 62 ms 74444 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 96 ms 88132 KB Output is correct
74 Correct 64 ms 78264 KB Output is correct
75 Correct 74 ms 84684 KB Output is correct
76 Correct 66 ms 78220 KB Output is correct
77 Correct 89 ms 85664 KB Output is correct
78 Correct 91 ms 85228 KB Output is correct
79 Correct 82 ms 76352 KB Output is correct
80 Correct 81 ms 77344 KB Output is correct
81 Correct 78 ms 79436 KB Output is correct
82 Correct 129 ms 141412 KB Output is correct
83 Correct 125 ms 140440 KB Output is correct
84 Correct 139 ms 148024 KB Output is correct
85 Correct 134 ms 143856 KB Output is correct
86 Correct 131 ms 145772 KB Output is correct
87 Correct 120 ms 147116 KB Output is correct
88 Correct 119 ms 143612 KB Output is correct
89 Correct 133 ms 142492 KB Output is correct
90 Correct 180 ms 152268 KB Output is correct
91 Correct 69 ms 74444 KB Output is correct
92 Correct 1 ms 468 KB Output is correct
93 Correct 69 ms 88024 KB Output is correct
94 Correct 60 ms 78164 KB Output is correct
95 Correct 80 ms 84692 KB Output is correct
96 Correct 72 ms 78188 KB Output is correct
97 Correct 84 ms 85696 KB Output is correct
98 Correct 97 ms 85340 KB Output is correct
99 Correct 91 ms 76136 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -