Submission #1215505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215505		zhenja	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	57 ms	328 KiB

sculpture

#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;

# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
    return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
    return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937 mt(time(0));
const int N = 2000 + 2, inf = 1e9 + 100, mod = 1e9 + 7, mod2 = 998244353, P = 257;
const ll llinf = 1e18 + 1000;
int n, lk, rk, a[N];
bool good(ll mask, int b, ll sum) {
    return ((mask >> b) | (sum >> b)) == (mask >> b);
}
bool check(ll mask, int b) {
    if (lk == 1) {
        vector<int> dp(n + 1, inf);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            ll sum = 0;
            for (int j = i; j >= 0; --j) {
                sum += a[j];
                if (good(mask, b, sum)) dp[i + 1] = min(dp[i + 1], dp[j] + 1);
            }
        }
        return dp[n] <= rk;
    } else {
        vector<vector<bool>> dp(n + 1, vector<bool>(n + 1));
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            ll sum = 0;
            for (int j = i; j >= 0; --j) {
                sum += a[j];
                if (!good(mask, b, sum)) continue;
                for (int c = 0; c <= j; ++c) {
                    dp[i + 1][c + 1] = dp[i + 1][c + 1] | dp[j][c];
                }
            }
        }
        for (int i = lk; i <= rk; ++i) {
            if (dp[n][i]) return true;
        }
        return false;
    }
}
void solve() {
    cin >> n >> lk >> rk;
    for (int i = 0; i < n; ++i) cin >> a[i];
    ll ans = 0;
    for (int b = 41; b >= 0; --b) {
        if (!check(ans, b)) ans += (1ll << b);
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("coloring.in", "r", stdin);
    //freopen("coloring.out", "w", stdout);

    //ld time1 = clock();

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
        cout.flush();
    }

    //ld time2 = clock();
    //cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
    return 0;
}

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