답안 #160150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160150	2019-10-26T07:23:42 Z	BlueDiamond	Bali Sculptures (APIO15_sculpture)	C++14	46 / 100	69 ms	20936 KB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll subtask1(int n, int l, int r, vector <int> a)
{
        ll ans = (1LL << 60);
        for (int mask = 1; mask < (1 << n); mask += 2)
        {
                int bits = 0, aux = mask;
                while (aux)
                {
                        bits++;
                        aux -= aux & (-aux);
                }
                if (l <= bits && bits <= r)
                {
                        ll curs = 0, cur = 0;
                        for (int i = 0; i < n; i++)
                        {
                                if (mask & (1 << i))
                                {
                                        cur |= curs;
                                        curs = 0;
                                }
                                curs += a[i];
                        }
                        cur |= curs;
                        ans = min(ans, cur);
                }
        }
        return ans;
}

ll subtask2(int n, int l, int r, vector <int> a)
{
        const int N = 50 + 1;
        const int L = 20 + 1;
        const int SM = 512 + 1;
        bool okoq[N][L][SM];

        for (int i = 0; i < N; i++)
                for (int j = 0; j < L; j++)
                        for (int k = 0; k < SM; k++)
                                okoq[i][j][k] = 0;

        okoq[0][0][0] = 1;
        for (int i = 0; i < n; i++)
                for (int cnt = 0; cnt < r; cnt++)
                        for (int x = 0; x < SM; x++)
                                if (okoq[i][cnt][x])
                                {
                                        int val = 0;
                                        for (int j = i + 1; j <= n; j++)
                                        {
                                                val += a[j - 1];
                                                okoq[j][cnt + 1][x | val] = 1;
                                        }
                                }
        int mn = 10000;
        for (int c = l; c <= r; c++)
                for (int x = 0; x < SM; x++)
                        if (okoq[n][c][x])
                                mn = min(mn, x);
        return mn;
}

bool okoq[101][101][2048];

ll subtask3(int n, int l, int r, vector <int> a)
{
        for (int i = 0; i <= 100; i++)
                for (int j = 0; j <= 100; j++)
                        for (int k = 0; k < 2048; k++)
                                okoq[i][j][k] = 0;



        okoq[0][0][0] = 1;
        for (int i = 0; i < n; i++)
                for (int cnt = 0; cnt < r; cnt++)
                        for (int x = 0; x < 2048; x++)
                                if (okoq[i][cnt][x])
                                {
                                        int val = 0;
                                        for (int j = i + 1; j <= n; j++)
                                        {
                                                val += a[j - 1];
                                                okoq[j][cnt + 1][x | val] = 1;
                                        }
                                }
        int mn = 10000;
        for (int c = l; c <= r; c++)
                for (int x = 0; x < 2048; x++)
                        if (okoq[n][c][x])
                                mn = min(mn, x);
        return mn;
}


int main()
{
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

       /// freopen ("input", "r", stdin);

        int n, l, r;
        cin >> n >> l >> r;
        vector <int> a(n);
        for (int i = 0; i < n; i++)
                cin >> a[i];

        if (n <= 100 && *max_element(a.begin(), a.end()) <= 20)
        {
                cout << subtask3(n, l, r, a) << "\n";
                return 0;
        }


        if (n <= 20)
        {
                cout << subtask1(n, l, r, a) << "\n";
                return 0;
        }

        if (n <= 50 && l <= 20 && r <= 20 && *max_element(a.begin(), a.end()) <= 10)
        {
                cout << subtask2(n, l, r, a) << "\n";
                return 0;
        }




        return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	20728 KB	Output is correct
2	Correct	28 ms	20728 KB	Output is correct
3	Correct	27 ms	20856 KB	Output is correct
4	Correct	27 ms	20772 KB	Output is correct
5	Correct	28 ms	20728 KB	Output is correct
6	Correct	28 ms	20728 KB	Output is correct
7	Correct	28 ms	20804 KB	Output is correct
8	Correct	27 ms	20728 KB	Output is correct
9	Correct	28 ms	20856 KB	Output is correct
10	Correct	27 ms	20728 KB	Output is correct
11	Correct	27 ms	20728 KB	Output is correct
12	Correct	28 ms	20728 KB	Output is correct
13	Correct	28 ms	20728 KB	Output is correct
14	Correct	27 ms	20728 KB	Output is correct
15	Correct	27 ms	20856 KB	Output is correct
16	Correct	27 ms	20728 KB	Output is correct
17	Correct	28 ms	20728 KB	Output is correct
18	Correct	28 ms	20832 KB	Output is correct
19	Correct	28 ms	20728 KB	Output is correct
20	Correct	27 ms	20728 KB	Output is correct
21	Correct	27 ms	20728 KB	Output is correct
22	Correct	28 ms	20856 KB	Output is correct
23	Correct	27 ms	20732 KB	Output is correct
24	Correct	27 ms	20828 KB	Output is correct
25	Correct	27 ms	20728 KB	Output is correct
26	Correct	28 ms	20728 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	4 ms	376 KB	Output is correct
31	Correct	9 ms	344 KB	Output is correct
32	Correct	6 ms	376 KB	Output is correct
33	Correct	41 ms	376 KB	Output is correct
34	Correct	46 ms	376 KB	Output is correct
35	Correct	6 ms	376 KB	Output is correct
36	Correct	44 ms	376 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	20728 KB	Output is correct
2	Correct	27 ms	20728 KB	Output is correct
3	Correct	26 ms	20728 KB	Output is correct
4	Correct	28 ms	20904 KB	Output is correct
5	Correct	27 ms	20728 KB	Output is correct
6	Correct	30 ms	20728 KB	Output is correct
7	Correct	28 ms	20856 KB	Output is correct
8	Correct	27 ms	20728 KB	Output is correct
9	Correct	28 ms	20728 KB	Output is correct
10	Correct	28 ms	20752 KB	Output is correct
11	Correct	27 ms	20728 KB	Output is correct
12	Correct	27 ms	20728 KB	Output is correct
13	Correct	28 ms	20816 KB	Output is correct
14	Correct	27 ms	20856 KB	Output is correct
15	Correct	28 ms	20728 KB	Output is correct
16	Correct	27 ms	20828 KB	Output is correct
17	Correct	26 ms	20728 KB	Output is correct
18	Correct	27 ms	20808 KB	Output is correct
19	Correct	27 ms	20856 KB	Output is correct
20	Correct	27 ms	20728 KB	Output is correct
21	Correct	28 ms	20728 KB	Output is correct
22	Correct	27 ms	20856 KB	Output is correct
23	Correct	27 ms	20728 KB	Output is correct
24	Correct	27 ms	20856 KB	Output is correct
25	Correct	27 ms	20856 KB	Output is correct
26	Correct	27 ms	20728 KB	Output is correct
27	Correct	27 ms	20728 KB	Output is correct
28	Correct	29 ms	20728 KB	Output is correct
29	Correct	27 ms	20728 KB	Output is correct
30	Correct	28 ms	20728 KB	Output is correct
31	Correct	31 ms	20728 KB	Output is correct
32	Correct	29 ms	20728 KB	Output is correct
33	Correct	28 ms	20728 KB	Output is correct
34	Correct	29 ms	20728 KB	Output is correct
35	Correct	29 ms	20728 KB	Output is correct
36	Correct	29 ms	20828 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	20856 KB	Output is correct
2	Correct	26 ms	20728 KB	Output is correct
3	Correct	26 ms	20728 KB	Output is correct
4	Correct	27 ms	20728 KB	Output is correct
5	Correct	27 ms	20728 KB	Output is correct
6	Correct	27 ms	20728 KB	Output is correct
7	Correct	28 ms	20860 KB	Output is correct
8	Correct	28 ms	20700 KB	Output is correct
9	Correct	27 ms	20728 KB	Output is correct
10	Correct	28 ms	20856 KB	Output is correct
11	Correct	32 ms	20728 KB	Output is correct
12	Correct	27 ms	20784 KB	Output is correct
13	Correct	28 ms	20728 KB	Output is correct
14	Correct	28 ms	20728 KB	Output is correct
15	Correct	27 ms	20728 KB	Output is correct
16	Correct	29 ms	20856 KB	Output is correct
17	Correct	29 ms	20728 KB	Output is correct
18	Correct	30 ms	20728 KB	Output is correct
19	Correct	29 ms	20728 KB	Output is correct
20	Correct	27 ms	20728 KB	Output is correct
21	Correct	29 ms	20856 KB	Output is correct
22	Correct	30 ms	20856 KB	Output is correct
23	Correct	29 ms	20728 KB	Output is correct
24	Correct	30 ms	20728 KB	Output is correct
25	Correct	31 ms	20756 KB	Output is correct
26	Correct	39 ms	20856 KB	Output is correct
27	Correct	52 ms	20732 KB	Output is correct
28	Correct	66 ms	20856 KB	Output is correct
29	Correct	61 ms	20820 KB	Output is correct
30	Correct	27 ms	20756 KB	Output is correct
31	Correct	61 ms	20816 KB	Output is correct
32	Correct	68 ms	20856 KB	Output is correct

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	20728 KB	Output is correct
2	Correct	27 ms	20728 KB	Output is correct
3	Correct	27 ms	20728 KB	Output is correct
4	Correct	27 ms	20712 KB	Output is correct
5	Correct	27 ms	20728 KB	Output is correct
6	Correct	28 ms	20728 KB	Output is correct
7	Correct	27 ms	20832 KB	Output is correct
8	Correct	27 ms	20728 KB	Output is correct
9	Correct	27 ms	20728 KB	Output is correct
10	Correct	27 ms	20856 KB	Output is correct
11	Correct	27 ms	20856 KB	Output is correct
12	Correct	27 ms	20728 KB	Output is correct
13	Correct	27 ms	20728 KB	Output is correct
14	Correct	28 ms	20728 KB	Output is correct
15	Correct	27 ms	20736 KB	Output is correct
16	Correct	27 ms	20728 KB	Output is correct
17	Correct	27 ms	20728 KB	Output is correct
18	Correct	27 ms	20728 KB	Output is correct
19	Correct	28 ms	20728 KB	Output is correct
20	Correct	34 ms	20728 KB	Output is correct
21	Correct	31 ms	20732 KB	Output is correct
22	Correct	33 ms	20700 KB	Output is correct
23	Correct	27 ms	20736 KB	Output is correct
24	Correct	26 ms	20728 KB	Output is correct
25	Correct	27 ms	20856 KB	Output is correct
26	Correct	28 ms	20856 KB	Output is correct
27	Correct	2 ms	504 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	6 ms	380 KB	Output is correct
31	Correct	9 ms	376 KB	Output is correct
32	Correct	6 ms	376 KB	Output is correct
33	Correct	46 ms	380 KB	Output is correct
34	Correct	46 ms	376 KB	Output is correct
35	Correct	6 ms	376 KB	Output is correct
36	Correct	44 ms	376 KB	Output is correct
37	Correct	28 ms	20728 KB	Output is correct
38	Correct	29 ms	20728 KB	Output is correct
39	Correct	27 ms	20856 KB	Output is correct
40	Correct	29 ms	20856 KB	Output is correct
41	Correct	32 ms	20768 KB	Output is correct
42	Correct	31 ms	20728 KB	Output is correct
43	Correct	31 ms	20728 KB	Output is correct
44	Correct	30 ms	20728 KB	Output is correct
45	Correct	29 ms	20748 KB	Output is correct
46	Correct	28 ms	20728 KB	Output is correct
47	Correct	30 ms	20796 KB	Output is correct
48	Correct	34 ms	20848 KB	Output is correct
49	Correct	38 ms	20856 KB	Output is correct
50	Correct	51 ms	20856 KB	Output is correct
51	Correct	67 ms	20732 KB	Output is correct
52	Correct	60 ms	20700 KB	Output is correct
53	Correct	27 ms	20728 KB	Output is correct
54	Correct	62 ms	20856 KB	Output is correct
55	Correct	68 ms	20852 KB	Output is correct
56	Incorrect	2 ms	376 KB	Output isn't correct
57	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	20856 KB	Output is correct
2	Correct	28 ms	20728 KB	Output is correct
3	Correct	27 ms	20728 KB	Output is correct
4	Correct	28 ms	20728 KB	Output is correct
5	Correct	28 ms	20728 KB	Output is correct
6	Correct	28 ms	20728 KB	Output is correct
7	Correct	28 ms	20728 KB	Output is correct
8	Correct	28 ms	20728 KB	Output is correct
9	Correct	27 ms	20856 KB	Output is correct
10	Correct	27 ms	20728 KB	Output is correct
11	Correct	28 ms	20860 KB	Output is correct
12	Correct	27 ms	20728 KB	Output is correct
13	Correct	28 ms	20732 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	4 ms	376 KB	Output is correct
18	Correct	9 ms	376 KB	Output is correct
19	Correct	6 ms	376 KB	Output is correct
20	Correct	41 ms	376 KB	Output is correct
21	Correct	45 ms	376 KB	Output is correct
22	Correct	6 ms	376 KB	Output is correct
23	Correct	44 ms	376 KB	Output is correct
24	Correct	28 ms	20728 KB	Output is correct
25	Correct	28 ms	20812 KB	Output is correct
26	Correct	47 ms	20728 KB	Output is correct
27	Correct	29 ms	20744 KB	Output is correct
28	Correct	30 ms	20728 KB	Output is correct
29	Correct	29 ms	20728 KB	Output is correct
30	Correct	28 ms	20756 KB	Output is correct
31	Correct	29 ms	20856 KB	Output is correct
32	Correct	29 ms	20728 KB	Output is correct
33	Correct	28 ms	20728 KB	Output is correct
34	Correct	30 ms	20728 KB	Output is correct
35	Correct	31 ms	20860 KB	Output is correct
36	Correct	38 ms	20736 KB	Output is correct
37	Correct	52 ms	20856 KB	Output is correct
38	Correct	66 ms	20856 KB	Output is correct
39	Correct	60 ms	20856 KB	Output is correct
40	Correct	27 ms	20816 KB	Output is correct
41	Correct	63 ms	20728 KB	Output is correct
42	Correct	69 ms	20936 KB	Output is correct
43	Incorrect	2 ms	376 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

답안 #160150

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0