oj.uz

답안 #559470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559470 2022-05-09T23:38:46 Z AlperenT Jelly Flavours (IOI20_jelly) C++17
33 / 100
 155 ms 152652 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));
			}
		}
	}

	for(int i = 0; i <= y; i++) ans = max(ans, dp2[0][i]);

	return ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
2 Correct 1 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 14 ms 13452 KB Output is correct
2 Correct 24 ms 20668 KB Output is correct
3 Correct 8 ms 5684 KB Output is correct
4 Correct 10 ms 8376 KB Output is correct
5 Correct 59 ms 53716 KB Output is correct
6 Correct 77 ms 68196 KB Output is correct
7 Correct 70 ms 65984 KB Output is correct
8 Correct 14 ms 13012 KB Output is correct
9 Correct 87 ms 69952 KB Output is correct
10 Correct 33 ms 28788 KB Output is correct
11 Correct 66 ms 61508 KB Output is correct
12 Correct 48 ms 48488 KB Output is correct
13 Correct 48 ms 42324 KB Output is correct
14 Correct 22 ms 13748 KB Output is correct
15 Correct 55 ms 48820 KB Output is correct
16 Correct 48 ms 46484 KB Output is correct
17 Correct 50 ms 49104 KB Output is correct
18 Correct 49 ms 52748 KB Output is correct
19 Correct 44 ms 41640 KB Output is correct
20 Correct 15 ms 13628 KB Output is correct
21 Correct 14 ms 13396 KB Output is correct
22 Correct 21 ms 20692 KB Output is correct
23 Correct 7 ms 5716 KB Output is correct
24 Correct 9 ms 8324 KB Output is correct
25 Correct 60 ms 53756 KB Output is correct
26 Correct 66 ms 68204 KB Output is correct
27 Correct 66 ms 65996 KB Output is correct
28 Correct 13 ms 13012 KB Output is correct
29 Correct 83 ms 69964 KB Output is correct
30 Correct 31 ms 28884 KB Output is correct
31 Correct 72 ms 61388 KB Output is correct
32 Correct 50 ms 48492 KB Output is correct
33 Correct 42 ms 42324 KB Output is correct
34 Correct 16 ms 13652 KB Output is correct
35 Correct 52 ms 48796 KB Output is correct
36 Correct 46 ms 46420 KB Output is correct
37 Correct 48 ms 49136 KB Output is correct
38 Correct 52 ms 52788 KB Output is correct
39 Correct 45 ms 41660 KB Output is correct
40 Correct 16 ms 13524 KB Output is correct
41 Correct 15 ms 13364 KB Output is correct
42 Correct 22 ms 20608 KB Output is correct
43 Correct 6 ms 5716 KB Output is correct
44 Correct 10 ms 8404 KB Output is correct
45 Correct 62 ms 53756 KB Output is correct
46 Correct 70 ms 68208 KB Output is correct
47 Correct 68 ms 65996 KB Output is correct
48 Correct 14 ms 13012 KB Output is correct
49 Correct 84 ms 70060 KB Output is correct
50 Correct 34 ms 28884 KB Output is correct
51 Correct 63 ms 61500 KB Output is correct
52 Correct 47 ms 48480 KB Output is correct
53 Correct 44 ms 42324 KB Output is correct
54 Correct 19 ms 13652 KB Output is correct
55 Correct 52 ms 48820 KB Output is correct
56 Correct 48 ms 46584 KB Output is correct
57 Correct 56 ms 49112 KB Output is correct
58 Correct 53 ms 52820 KB Output is correct
59 Correct 48 ms 41684 KB Output is correct
60 Correct 15 ms 13524 KB Output is correct
61 Correct 14 ms 13396 KB Output is correct
62 Correct 21 ms 20812 KB Output is correct
63 Correct 7 ms 5844 KB Output is correct
64 Correct 10 ms 8404 KB Output is correct
65 Correct 62 ms 53748 KB Output is correct
66 Correct 83 ms 68196 KB Output is correct
67 Correct 64 ms 65956 KB Output is correct
68 Correct 13 ms 13012 KB Output is correct
69 Correct 74 ms 69952 KB Output is correct
70 Correct 31 ms 28900 KB Output is correct
71 Correct 63 ms 61504 KB Output is correct
72 Correct 49 ms 48488 KB Output is correct
73 Correct 44 ms 42236 KB Output is correct
74 Correct 15 ms 13652 KB Output is correct
75 Correct 52 ms 48840 KB Output is correct
76 Correct 45 ms 46508 KB Output is correct
77 Correct 51 ms 49180 KB Output is correct
78 Correct 53 ms 52820 KB Output is correct
79 Correct 52 ms 41692 KB Output is correct
80 Correct 15 ms 13524 KB Output is correct
81 Correct 14 ms 13396 KB Output is correct
82 Correct 22 ms 20692 KB Output is correct
83 Correct 6 ms 5716 KB Output is correct
84 Correct 9 ms 8404 KB Output is correct
85 Correct 56 ms 53716 KB Output is correct
86 Correct 68 ms 68136 KB Output is correct
87 Correct 63 ms 65868 KB Output is correct
88 Correct 13 ms 13112 KB Output is correct
89 Correct 74 ms 70064 KB Output is correct
90 Correct 35 ms 28880 KB Output is correct
91 Correct 65 ms 61444 KB Output is correct
92 Correct 47 ms 48484 KB Output is correct
93 Correct 42 ms 42340 KB Output is correct
94 Correct 14 ms 13760 KB Output is correct
95 Correct 52 ms 48820 KB Output is correct
96 Correct 44 ms 46452 KB Output is correct
97 Correct 53 ms 49164 KB Output is correct
98 Correct 54 ms 52896 KB Output is correct
99 Correct 47 ms 41644 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 81600 KB Output is correct
2 Correct 132 ms 146612 KB Output is correct
3 Correct 137 ms 145004 KB Output is correct
4 Correct 155 ms 148404 KB Output is correct
5 Correct 147 ms 152568 KB Output is correct
6 Correct 123 ms 144460 KB Output is correct
7 Correct 117 ms 145220 KB Output is correct
8 Correct 121 ms 147772 KB Output is correct
9 Correct 147 ms 142156 KB Output is correct
10 Correct 146 ms 146624 KB Output is correct
11 Correct 57 ms 79052 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 55 ms 73680 KB Output is correct
14 Correct 60 ms 75660 KB Output is correct
15 Correct 64 ms 77672 KB Output is correct
16 Correct 51 ms 72780 KB Output is correct
17 Correct 87 ms 73036 KB Output is correct
18 Correct 75 ms 82800 KB Output is correct
19 Correct 86 ms 82764 KB Output is correct
20 Correct 75 ms 70840 KB Output is correct
21 Correct 75 ms 81596 KB Output is correct
22 Correct 115 ms 146624 KB Output is correct
23 Correct 119 ms 144984 KB Output is correct
24 Correct 139 ms 148308 KB Output is correct
25 Correct 143 ms 152568 KB Output is correct
26 Correct 122 ms 144344 KB Output is correct
27 Correct 118 ms 145292 KB Output is correct
28 Correct 114 ms 147732 KB Output is correct
29 Correct 139 ms 142092 KB Output is correct
30 Correct 139 ms 146592 KB Output is correct
31 Correct 54 ms 79116 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 53 ms 73764 KB Output is correct
34 Correct 60 ms 75656 KB Output is correct
35 Correct 61 ms 77652 KB Output is correct
36 Correct 49 ms 72748 KB Output is correct
37 Correct 71 ms 73116 KB Output is correct
38 Correct 75 ms 82928 KB Output is correct
39 Correct 87 ms 82784 KB Output is correct
40 Correct 73 ms 70740 KB Output is correct
41 Correct 74 ms 81700 KB Output is correct
42 Correct 120 ms 146664 KB Output is correct
43 Correct 116 ms 144820 KB Output is correct
44 Correct 136 ms 148348 KB Output is correct
45 Correct 140 ms 152652 KB Output is correct
46 Correct 121 ms 144464 KB Output is correct
47 Correct 115 ms 145312 KB Output is correct
48 Correct 114 ms 147764 KB Output is correct
49 Correct 133 ms 142068 KB Output is correct
50 Correct 136 ms 146616 KB Output is correct
51 Correct 56 ms 79080 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 55 ms 73788 KB Output is correct
54 Correct 62 ms 75684 KB Output is correct
55 Correct 66 ms 77680 KB Output is correct
56 Correct 51 ms 72768 KB Output is correct
57 Correct 94 ms 73228 KB Output is correct
58 Correct 78 ms 82812 KB Output is correct
59 Correct 93 ms 82764 KB Output is correct
60 Correct 76 ms 70740 KB Output is correct
61 Correct 74 ms 81592 KB Output is correct
62 Correct 116 ms 146552 KB Output is correct
63 Correct 116 ms 144928 KB Output is correct
64 Correct 141 ms 148408 KB Output is correct
65 Correct 140 ms 152600 KB Output is correct
66 Correct 120 ms 144332 KB Output is correct
67 Correct 117 ms 145228 KB Output is correct
68 Correct 115 ms 147700 KB Output is correct
69 Correct 136 ms 142044 KB Output is correct
70 Correct 138 ms 146496 KB Output is correct
71 Correct 54 ms 79112 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 54 ms 73692 KB Output is correct
74 Correct 61 ms 75676 KB Output is correct
75 Correct 62 ms 77652 KB Output is correct
76 Correct 49 ms 72732 KB Output is correct
77 Correct 69 ms 73036 KB Output is correct
78 Correct 77 ms 82812 KB Output is correct
79 Correct 85 ms 82784 KB Output is correct
80 Correct 72 ms 70836 KB Output is correct
81 Correct 74 ms 81704 KB Output is correct
82 Correct 119 ms 146680 KB Output is correct
83 Correct 123 ms 144840 KB Output is correct
84 Correct 140 ms 148300 KB Output is correct
85 Correct 143 ms 152612 KB Output is correct
86 Correct 123 ms 144460 KB Output is correct
87 Correct 119 ms 145296 KB Output is correct
88 Correct 117 ms 147656 KB Output is correct
89 Correct 133 ms 142092 KB Output is correct
90 Correct 140 ms 146576 KB Output is correct
91 Correct 54 ms 79112 KB Output is correct
92 Correct 1 ms 468 KB Output is correct
93 Correct 52 ms 73700 KB Output is correct
94 Correct 62 ms 75596 KB Output is correct
95 Correct 66 ms 77612 KB Output is correct
96 Correct 56 ms 72780 KB Output is correct
97 Correct 71 ms 72996 KB Output is correct
98 Correct 75 ms 82812 KB Output is correct
99 Correct 84 ms 82780 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 79460 KB Output is correct
2 Correct 121 ms 141448 KB Output is correct
3 Correct 120 ms 140456 KB Output is correct
4 Correct 139 ms 147968 KB Output is correct
5 Correct 133 ms 143820 KB Output is correct
6 Correct 129 ms 145780 KB Output is correct
7 Correct 117 ms 147016 KB Output is correct
8 Correct 116 ms 143612 KB Output is correct
9 Correct 132 ms 142424 KB Output is correct
10 Correct 140 ms 152304 KB Output is correct
11 Correct 59 ms 74460 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 67 ms 88012 KB Output is correct
14 Correct 64 ms 78256 KB Output is correct
15 Correct 71 ms 84604 KB Output is correct
16 Correct 61 ms 78248 KB Output is correct
17 Correct 83 ms 85700 KB Output is correct
18 Correct 86 ms 85320 KB Output is correct
19 Correct 86 ms 76160 KB Output is correct
20 Correct 79 ms 77332 KB Output is correct
21 Correct 79 ms 79420 KB Output is correct
22 Correct 118 ms 141388 KB Output is correct
23 Correct 114 ms 140476 KB Output is correct
24 Correct 137 ms 147992 KB Output is correct
25 Correct 133 ms 143816 KB Output is correct
26 Correct 117 ms 145740 KB Output is correct
27 Correct 117 ms 147096 KB Output is correct
28 Correct 122 ms 143564 KB Output is correct
29 Correct 133 ms 142412 KB Output is correct
30 Correct 144 ms 152300 KB Output is correct
31 Correct 61 ms 74368 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 72 ms 88072 KB Output is correct
34 Correct 67 ms 78248 KB Output is correct
35 Correct 74 ms 84720 KB Output is correct
36 Correct 60 ms 78204 KB Output is correct
37 Correct 83 ms 85708 KB Output is correct
38 Correct 84 ms 85284 KB Output is correct
39 Correct 81 ms 76196 KB Output is correct
40 Correct 80 ms 77236 KB Output is correct
41 Correct 77 ms 79500 KB Output is correct
42 Correct 115 ms 141428 KB Output is correct
43 Correct 117 ms 140380 KB Output is correct
44 Correct 142 ms 148124 KB Output is correct
45 Correct 135 ms 143840 KB Output is correct
46 Correct 115 ms 145780 KB Output is correct
47 Correct 118 ms 147020 KB Output is correct
48 Correct 118 ms 143692 KB Output is correct
49 Correct 144 ms 142428 KB Output is correct
50 Correct 145 ms 152232 KB Output is correct
51 Correct 58 ms 74452 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 72 ms 88112 KB Output is correct
54 Correct 65 ms 78284 KB Output is correct
55 Correct 73 ms 84736 KB Output is correct
56 Correct 65 ms 78252 KB Output is correct
57 Correct 84 ms 85736 KB Output is correct
58 Correct 85 ms 85196 KB Output is correct
59 Correct 83 ms 76244 KB Output is correct
60 Correct 92 ms 77340 KB Output is correct
61 Correct 99 ms 79436 KB Output is correct
62 Correct 121 ms 141512 KB Output is correct
63 Correct 119 ms 140480 KB Output is correct
64 Correct 147 ms 147892 KB Output is correct
65 Correct 145 ms 143964 KB Output is correct
66 Correct 117 ms 145744 KB Output is correct
67 Correct 117 ms 147104 KB Output is correct
68 Correct 117 ms 143560 KB Output is correct
69 Correct 140 ms 142348 KB Output is correct
70 Correct 145 ms 152212 KB Output is correct
71 Correct 60 ms 74412 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 70 ms 88120 KB Output is correct
74 Correct 62 ms 78164 KB Output is correct
75 Correct 79 ms 84708 KB Output is correct
76 Correct 60 ms 78196 KB Output is correct
77 Correct 91 ms 85716 KB Output is correct
78 Correct 84 ms 85328 KB Output is correct
79 Correct 82 ms 76188 KB Output is correct
80 Correct 85 ms 77260 KB Output is correct
81 Correct 77 ms 79440 KB Output is correct
82 Correct 114 ms 141384 KB Output is correct
83 Correct 115 ms 140372 KB Output is correct
84 Correct 134 ms 147988 KB Output is correct
85 Correct 142 ms 143804 KB Output is correct
86 Correct 116 ms 145736 KB Output is correct
87 Correct 128 ms 146972 KB Output is correct
88 Correct 114 ms 143616 KB Output is correct
89 Correct 134 ms 142412 KB Output is correct
90 Correct 141 ms 152304 KB Output is correct
91 Correct 57 ms 74464 KB Output is correct
92 Correct 1 ms 468 KB Output is correct
93 Correct 71 ms 88140 KB Output is correct
94 Correct 63 ms 78188 KB Output is correct
95 Correct 72 ms 84664 KB Output is correct
96 Correct 62 ms 78336 KB Output is correct
97 Correct 82 ms 85740 KB Output is correct
98 Correct 81 ms 85248 KB Output is correct
99 Correct 78 ms 76240 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 -