oj.uz

Submission #160149

# Submission time Handle Problem Language Result Execution time Memory
160149 2019-10-26T07:22:58 Z BlueDiamond Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 39 ms 20856 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 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 << "Subtask 3\n";
                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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 20728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 20728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 20732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 20856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 20704 KB Output isn't correct
2 Halted 0 ms 0 KB -