제출 #1357829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357829		Agageldi	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	271 ms	956 KiB

sculpture

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

#define N 2001
#define int long long

const int inf = INT_MAX;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, a[N], B, A, b[N], ans = -1, M = 0;
bitset <N + 1> dp[N];

bool check(int x) {
    for(int i = 1; i <= n; i++) {
        dp[i].reset();
    }

    dp[0] = 1;

    for(int i = 0; i <= n; i++) {
        int s = 0;
        if(!dp[i].any()) continue;
        bitset <N + 1> sh = (dp[i] << 1);
        for(int j = i + 1; j <= n; j++){
            s += a[j];
            if(!(s & (~x))) {
                dp[j] |= sh;
            }
        }
    }
    for(int i = A;i <= B; i++) {
        if(dp[n].test(i)) return 1;
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 60; i >= 0; i--) {
        int num = M | ((1ll<<i) - 1);
        if(!check(num)){
            M |= (1ll << i);
        }
    }
    cout << M << '\n';
    return 0;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 16 / 16
• 서브태스크 3: 21 / 21
• 서브태스크 4: 25 / 25
• 서브태스크 5: 29 / 29