제출 #499091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499091		cig32	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1076 ms	712 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
void solve(int tc) {
    int n, A, B;
    cin >> n >> A >> B;
    int a[n+1];
    for(int i=1; i<=n; i++) cin >> a[i];
    int ps[n+1];
    ps[0] = 0;
    for(int i=1; i<=n; i++) ps[i] = ps[i-1] + a[i];
    int ans = 1e18;
    for(int k=A; k<=B; k++) {
        int msk = 0;
        for(int bit=44; bit>=0; bit--) {
            int dp[k+1][n+1];
            for(int i=0; i<=k; i++) {
                for(int j=0; j<=n; j++) {
                    dp[i][j] = 0;
                }
            }
            for(int i=1; i<=n; i++) dp[1][i] = ((ps[i] & (msk + (1ll << bit))) == 0);
            for(int i=2; i<=k; i++) {
                for(int j=i; j<=n; j++) {
                    for(int l=i-1; l<j; l++) {
                        int wow = ps[j] - ps[l];
                        if((wow & (msk + (1ll << bit))) == 0) {
                            dp[i][j] |= dp[i-1][l];
                        }
                    }
                }
            }
            if(dp[k][n]) {
                msk += (1ll << bit);
            }
        }
        ans = min(ans, (1ll << 45) - 1 - msk);
    }
    cout << ans << endl;
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
} 

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