제출 #1358897

#제출 시각아이디문제언어결과실행 시간메모리
1358897nathlol2Bali Sculptures (APIO15_sculpture)C++20
0 / 100
6 ms4420 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, a, b, ans, y[N], pf[N][31];
bool dp[N][N];
vector<int> can[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> a >> b;
    for(int i = 1;i<=n;i++){
        cin >> y[i];
        for(int bit = 0;bit<=30;bit++){
            pf[i][bit] = pf[i - 1][bit];
            if(y[i] & (1 << bit)) pf[i][bit]++;
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = max(0, i - b);j<=i - a;j++) can[i].push_back(j);
    }
    for(int bit = 30;bit>=0;bit--){
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        vector<int> ncan[N];
        for(int k = 1;k<=b;k++){
            for(int i = 1;i<=n;i++){
                for(auto x : can[i]){
                    if((pf[i][bit] - pf[x][bit]) % 2 == 0){
                        dp[i][k] |= dp[x][k - 1];
                        if(k == 1) ncan[i].push_back(x);
                    }
                }
            }
        }
        bool ok = 0;
        for(int i = a;i<=b;i++) ok |= dp[n][i];
        if(ok){
            for(int i = 1;i<=n;i++) can[i] = ncan[i];
        }else{
            ans += (1 << bit);
        }
    }
    cout << ans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…