답안 #160146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160146	2019-10-26T07:15:29 Z	BlueDiamond	Bali Sculptures (APIO15_sculpture)	C++14	25 / 100	44 ms	892 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 ok[N][L][SM];

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

        ok[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 (ok[i][cnt][x])
                                {
                                        int val = 0;
                                        for (int j = i + 1; j <= n; j++)
                                        {
                                                val += a[j - 1];
                                                ok[j][cnt + 1][x | val] = 1;
                                        }
                                }
        int mn = 10000;
        for (int c = l; c <= r; c++)
                for (int x = 0; x < SM; x++)
                        if (ok[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 <= 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	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	6 ms	376 KB	Output is correct
9	Correct	7 ms	376 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	15 ms	376 KB	Output is correct
13	Correct	43 ms	376 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	2 ms	256 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	9 ms	296 KB	Output is correct
22	Correct	9 ms	376 KB	Output is correct
23	Correct	9 ms	376 KB	Output is correct
24	Correct	6 ms	376 KB	Output is correct
25	Correct	10 ms	256 KB	Output is correct
26	Correct	41 ms	376 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	252 KB	Output is correct
31	Correct	9 ms	376 KB	Output is correct
32	Correct	6 ms	376 KB	Output is correct
33	Correct	41 ms	376 KB	Output is correct
34	Correct	43 ms	376 KB	Output is correct
35	Correct	6 ms	376 KB	Output is correct
36	Correct	43 ms	348 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	6 ms	372 KB	Output is correct
9	Correct	6 ms	376 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	43 ms	504 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	3 ms	376 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	11 ms	376 KB	Output is correct
22	Correct	9 ms	376 KB	Output is correct
23	Correct	9 ms	376 KB	Output is correct
24	Correct	6 ms	376 KB	Output is correct
25	Correct	9 ms	376 KB	Output is correct
26	Correct	40 ms	380 KB	Output is correct
27	Correct	3 ms	888 KB	Output is correct
28	Correct	3 ms	888 KB	Output is correct
29	Correct	3 ms	888 KB	Output is correct
30	Correct	3 ms	888 KB	Output is correct
31	Correct	5 ms	888 KB	Output is correct
32	Correct	4 ms	888 KB	Output is correct
33	Correct	3 ms	888 KB	Output is correct
34	Correct	4 ms	888 KB	Output is correct
35	Correct	5 ms	888 KB	Output is correct
36	Correct	4 ms	888 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	6 ms	376 KB	Output is correct
9	Correct	6 ms	376 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	44 ms	376 KB	Output is correct
14	Correct	3 ms	888 KB	Output is correct
15	Correct	3 ms	892 KB	Output is correct
16	Correct	3 ms	892 KB	Output is correct
17	Correct	4 ms	888 KB	Output is correct
18	Correct	5 ms	888 KB	Output is correct
19	Correct	4 ms	888 KB	Output is correct
20	Correct	3 ms	888 KB	Output is correct
21	Correct	5 ms	888 KB	Output is correct
22	Correct	4 ms	888 KB	Output is correct
23	Correct	4 ms	892 KB	Output is correct
24	Incorrect	2 ms	256 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	380 KB	Output is correct
8	Correct	6 ms	376 KB	Output is correct
9	Correct	6 ms	376 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	44 ms	380 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	2 ms	376 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	9 ms	376 KB	Output is correct
22	Correct	9 ms	376 KB	Output is correct
23	Correct	11 ms	372 KB	Output is correct
24	Correct	6 ms	376 KB	Output is correct
25	Correct	9 ms	376 KB	Output is correct
26	Correct	40 ms	504 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	376 KB	Output is correct
32	Correct	6 ms	376 KB	Output is correct
33	Correct	41 ms	504 KB	Output is correct
34	Correct	43 ms	372 KB	Output is correct
35	Correct	6 ms	376 KB	Output is correct
36	Correct	44 ms	376 KB	Output is correct
37	Correct	14 ms	888 KB	Output is correct
38	Correct	3 ms	888 KB	Output is correct
39	Correct	3 ms	888 KB	Output is correct
40	Correct	4 ms	888 KB	Output is correct
41	Correct	5 ms	888 KB	Output is correct
42	Correct	4 ms	888 KB	Output is correct
43	Correct	3 ms	888 KB	Output is correct
44	Correct	4 ms	888 KB	Output is correct
45	Correct	4 ms	888 KB	Output is correct
46	Correct	4 ms	888 KB	Output is correct
47	Incorrect	2 ms	380 KB	Output isn't correct
48	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	7 ms	376 KB	Output is correct
9	Correct	6 ms	376 KB	Output is correct
10	Correct	6 ms	256 KB	Output is correct
11	Correct	20 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	43 ms	376 KB	Output is correct
14	Correct	2 ms	256 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	44 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	3 ms	888 KB	Output is correct
25	Correct	3 ms	888 KB	Output is correct
26	Correct	3 ms	888 KB	Output is correct
27	Correct	4 ms	888 KB	Output is correct
28	Correct	8 ms	892 KB	Output is correct
29	Correct	4 ms	888 KB	Output is correct
30	Correct	3 ms	892 KB	Output is correct
31	Correct	4 ms	888 KB	Output is correct
32	Correct	4 ms	888 KB	Output is correct
33	Correct	4 ms	888 KB	Output is correct
34	Incorrect	2 ms	376 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #160146

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 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
0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0