Submission #469852

#	Time	Username	Problem	Language	Result	Execution time	Memory
469852		amirmohammad_nezami	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	140 ms	4312 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define _sz(e) (int)e.size()
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse4,avx,avx2")

const ll maxn = 2e3 + 4 , N = 2e6 + 4 , mod = 1e9 + 7 , INF = 1e9 + 4 , lg = 43;

ll n , A , B , a[maxn] , ps[maxn] , mn[maxn] , ans = (1ll << lg) - 1;
bool dp[maxn][maxn];

bool check_sub(ll x) {
    fill(mn , mn + maxn , INF);
    memset(dp , 0 , sizeof dp);
    mn[0] = 0 , dp[0][0] = 1;

    if(n <= 200) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                for (int t = 1; t <= i; ++t) {
                    ll sum = ps[i] - ps[i - t];
                    if((sum | x) != x) continue;
                    dp[i][j] |= dp[i - t][j - 1];
                }
            }
        }
        bool res = 0;
        for (int i = A; i <= B; ++i) {
            res |= dp[n][i];
        }
        return res;
    }
    else {
        for (int i = 1; i <= n; ++i) {
            for (int t = 1; t <= i; ++t) {
                ll sum = ps[i] - ps[i - t];
                if((sum | x) != x) continue;
                mn[i] = min(mn[i] , mn[i - t] + 1);
            }
        }
        return (mn[n] <= B);
    }
}

int main() {
    FAST;
    cin >> n >> A >> B;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ps[i + 1] = ps[i] + a[i];
    }

    for (int i = lg - 1; i >= 0; --i) {
        if(check_sub(ans - (1ll << i))) {
            ans -= (1ll << i);
        }
    }
    cout << ans << '\n';
}

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