Submission #622409

#	Time	Username	Problem	Language	Result	Execution time	Memory
622409		socpite	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	219 ms	464 KiB

sculpture

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

#define f first
#define s second

typedef long long ll;

const int maxn = 2e3+5;
const int inf = 1e9;

int dp[maxn];
bitset<105> chim[105];
int A[maxn];

int n, l, r;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //ifstream cin("input.txt");
    ll ans = (1LL<<60)-1;
    cin >> n >> l >> r;
    chim[0][0]=1;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    for(int p = 59; p >= 0; p--){
        ans^=(1LL<<p);
        if(l > 1){
            for(int i = 1; i <= n; i++){
                chim[i].reset();
                ll sum = 0;
                for(int j = i; j > 0; j--){
                    sum+=A[j];
                    if((ans|sum) == ans)chim[i]|=chim[j-1]<<1;
                }
            }
            for(int i = l; i <= r; i++)if(chim[n][i]){
                ans^=(1LL<<p);
                break;
            }
            ans^=(1LL<<p);
        }
        else{
            for(int i = 1; i <= n; i++){
                dp[i]=inf;
                ll sum = 0;
                for(int j = i; j > 0; j--){
                    sum+=A[j];
                    if((ans|sum) == ans)dp[i]=min(dp[i], dp[j-1]+1);
                }
            }
            if(dp[n] > r)ans^=(1LL<<p);
        }
    }
    cout << ans;

}

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