Submission #602478

#	Time	Username	Problem	Language	Result	Execution time	Memory
602478		snasibov05	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	35 ms	312 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define oo 1000000000000000000ll

int main() {
    int n, a, b; cin >> n >> a >> b;
    vector<int> y(n+1);
    for (int i = 1; i <= n; ++i) cin >> y[i];

    vector<long long> pref(n+1);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i-1] + 1ll*y[i];

    const int mx = 45;
    long long ans = 0;
    for (int bt = mx-1; bt >= 0 && n <= 100; --bt){
        vector<vector<bool>> dp(n+1, vector<bool>(b+1)); dp[0][0] = true;
        ans = ans | (1ll << bt);
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= min(i, b); ++j){
                for (int prev = 0; prev < i; ++prev){
                    if (!((pref[i] - pref[prev]) & ans) && dp[prev][j-1]) dp[i][j] = true;
                }
            }
        }

        bool flag = false;
        for (int i = a; i <= b; ++i){
            if (dp[n][i]) flag = true;
        }

        if (!flag) ans = ans ^ (1ll << bt);
    }

    for (int bt = mx-1; bt >= 0 && n > 100; --bt){
        vector<int> dp(n+1, n+1); dp[0] = 0;
        ans = ans | (1ll << bt);
        for (int i = 1; i <= n; ++i){
            for (int prev = 0; prev < i; ++prev){
                if (!((pref[i] - pref[prev]) & ans) && dp[prev]) dp[i] = min(dp[i], dp[prev] + 1);
            }
        }

        if (dp[n] > b) ans = ans ^ (1ll << bt);
    }

    ans = ans ^ ((1ll << mx) - 1ll);
    cout << ans << "\n";

    return 0;
}

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