Submission #41394

#	Time	Username	Problem	Language	Result	Execution time	Memory
41394		krauch	Bali Sculptures (APIO15_sculpture)	C++14	46 / 100	88 ms	1708 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define y1 kekek
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 2e3 + 6, oo = 1e9 + 9, base = 1e9 + 7;

int n, A, B, a[N], d[N][N], d2[55][22][555];
ll ans = ool;
bool bit[22];

void rec(int pos, int cnt) {
    if (cnt > B) return;
    if (pos == n + 1) {
        if (cnt < A) return;
        ll res = 0, sum = 0;
        forn(i, 1, n) {
            if (i > 1 && bit[i] != bit[i - 1]) {
                res |= sum;
                sum = 0;
            }
            sum += a[i];
        }
        res |= sum;

        ans = min(ans, res);
        return;
    }

    bit[pos] = 0;
    rec(pos + 1, cnt + (pos == 1 || bit[pos] != bit[pos - 1]));
    bit[pos] = 1;
    rec(pos + 1, cnt + (pos == 1 || bit[pos] != bit[pos - 1]));
}

int main() {
    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n >> A >> B;
    forn(i, 1, n) {
        cin >> a[i];
    }

    if (n <= 20) {
        rec(1, 0);
        cout << ans << "\n";
        return 0;
    }

    if (A > 1) {
        d2[0][0][0] = 1;
        forn(i, 1, n) {
            forn(j, 1, B) {
                int sum = 0;
                for1(k, i, 1) {
                    sum += a[k];
                    forn(l, 0, 500) {
                        d2[i][j][l | sum] |= d2[k - 1][j - 1][l];
                    }
                }
            }
        }
        int mn = oo;
        forn(i, A, B) {
            forn(j, 0, 500) {
                if (d2[n][i][j]) mn = min(mn, j);
            }
        }

        cout << mn << "\n";

        return 0;
    }

    forn(j, 0, 2000) d[0][j] = oo;
    d[0][0] = 0;

    forn(i, 1, n) {
        int sum = 0;
        forn(j, 0, 2000) d[i][j] = oo;
        for1(j, i, 1) {
            sum += a[j];
            forn(k, 0, 2000) {
                d[i][k | sum] = min(d[i][k | sum], d[j - 1][k] + 1);
            }
        }
    }

    int pos = 2000;
    forn(i, 0, 2000) {
        if (d[n][i] <= B) {
            pos = i;
            break;
        }
    }
    cout << pos << "\n";

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29