제출 #925493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925493		VMaksimoski008	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	127 ms	600 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int32_t main() {
    int n, a, b;
    cin >> n >> a >> b;
 
    vector<ll> pref(n+1);    
    for(int i=1; i<=n; i++) cin >> pref[i], pref[i] += pref[i-1];
 
    auto query = [&](int l, int r) { return pref[r] - pref[l-1]; };
 
    if(a == 1) {
        ll mask = 0;
        for(int bit=51; bit>=0; bit--) {
            mask |= (1ll << bit);
            vector<int> dp(n+1, 1e9);
            dp[0] = 0;
 
            for(int i=1; i<=n; i++) {
                for(int j=i; j>=1; j--) {
                    if(query(j, i) & mask) continue;
                    dp[i] = min(dp[i], dp[j-1] + 1);
                }
            }
            
            if(dp[n] > b) mask ^= (1ll << bit);
        }
 
        mask ^= ((1ll << 52) - 1);
        cout << mask << '\n';
        return 0;
    }
 
    ll mask = 0;
    bool dp[n+1][n+1];
    for(int bit=51; bit>=0; bit--) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        mask |= (1ll << bit);

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=i; j++) {
                for(int k=1; k<=i; k++) {
                    if(query(k, i) & mask) continue;
                    if(dp[k-1][j-1]) dp[i][j] = 1;
                }
            }
        }

        bool ok = 0;
        for(int j=a; j<=b; j++) ok |= dp[n][j];
        if(!ok) mask ^= (1ll << bit); 
    }

    mask ^= ((1ll << 52) - 1);
    cout << mask << '\n';
	return 0;
}

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