Submission #331007

#	Time	Username	Problem	Language	Result	Execution time	Memory
331007		couplefire	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	533 ms	22000 KiB

sculpture

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

int n, a, b;
long long arr[2005];
long long prefix[2005];
vector<vector<int>> v;
long long res = 0;

inline long long sum(int i, int j){
    if(i > j) swap(i, j);
    return prefix[j]-prefix[i-1];
}

bool check(vector<vector<int>> &tmp){
    if(n>100){
        int dp[n+1]; fill(dp, dp+n+1, n+1);
        dp[0] = 0;
        for(int i = 1; i<=n; i++){
            for(auto j : tmp[i]) dp[i] = min(dp[j-1]+1, dp[i]);
        }
        if(dp[n] == -1 || dp[n] > b) return false;
        return 1;
    }
    bitset<105> dp[n+1];
    dp[0].reset();
    dp[0].set(0);
    for(int i = 1; i<=n; i++){
        dp[i].reset();
        for(int j : tmp[i]) dp[i] |= (dp[j-1]<<1); 
    }
    for(int i = a; i<=b; i++){
        if(dp[n].test(i)) return 1;
    }
    return 0;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i<=n; i++) cin >> arr[i];
    prefix[0] = 0;
    for(int i = 1; i<=n; i++) prefix[i] = prefix[i-1]+arr[i];
    v.resize(n+1);
    for(int i = 1; i<=n; i++){
        for(int j = i; j<=n; j++){
            v[j].push_back(i);
        }
    }
    for(int m = 60; m>=0; m--){
        vector<vector<int>> tmp;
        tmp.resize(n+1);
        for(int i = 1; i<=n; i++){
            for(auto &x : v[i]){
                if(sum(x, i)&(1ll<<m)) continue;
                else tmp[i].push_back(x);
            }
        }
        if(check(tmp)){
            v = tmp;
        }
        else res += 1ll<<m;
    }
    cout << res << endl;
}

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