oj.uz

Submission #160147

# Submission time Handle Problem Language Result Execution time Memory
160147 2019-10-26T07:16:45 Z BlueDiamond Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 46 ms 1016 KB 
#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;
}

ll subtask3(int n, int l, int r, vector <int> a)
{
        const int N = 100 + 1;
        const int L = 100 + 1;
        const int SM = 2048 + 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

# Verdict Execution time Memory 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 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 2 ms 376 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 256 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 380 KB Output is correct
14 Correct 3 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 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 9 ms 376 KB Output is correct
22 Correct 10 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 256 KB Output is correct
26 Correct 43 ms 256 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 252 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 40 ms 376 KB Output is correct
34 Correct 44 ms 416 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 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 256 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 6 ms 256 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 46 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 376 KB Output is correct
18 Correct 2 ms 252 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 252 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 11 ms 504 KB Output is correct
26 Correct 41 ms 376 KB Output is correct
27 Correct 3 ms 892 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 892 KB Output is correct
31 Correct 5 ms 888 KB Output is correct
32 Correct 4 ms 892 KB Output is correct
33 Correct 3 ms 888 KB Output is correct
34 Correct 4 ms 888 KB Output is correct
35 Correct 4 ms 888 KB Output is correct
36 Correct 4 ms 888 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory 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 18 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 45 ms 380 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 888 KB Output is correct
16 Correct 3 ms 888 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 4 ms 888 KB Output is correct
22 Correct 4 ms 888 KB Output is correct
23 Correct 4 ms 888 KB Output is correct
24 Incorrect 2 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 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 6 ms 376 KB Output is correct
10 Correct 6 ms 256 KB Output is correct
11 Correct 7 ms 504 KB Output is correct
12 Correct 8 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 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 380 KB Output is correct
21 Correct 10 ms 376 KB Output is correct
22 Correct 11 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 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 376 KB Output is correct
31 Correct 10 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 45 ms 292 KB Output is correct
35 Correct 6 ms 376 KB Output is correct
36 Correct 44 ms 256 KB Output is correct
37 Correct 3 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 860 KB Output is correct
43 Correct 3 ms 892 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 256 KB Output isn't correct
48 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 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 380 KB Output is correct
9 Correct 12 ms 380 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 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 380 KB Output is correct
17 Correct 4 ms 380 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 43 ms 376 KB Output is correct
22 Correct 6 ms 252 KB Output is correct
23 Correct 43 ms 256 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 3 ms 888 KB Output is correct
28 Correct 5 ms 1016 KB Output is correct
29 Correct 4 ms 888 KB Output is correct
30 Correct 3 ms 888 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 892 KB Output is correct
34 Incorrect 2 ms 376 KB Output isn't correct
35 Halted 0 ms 0 KB -