Submission #1358902

#TimeUsernameProblemLanguageResultExecution timeMemory
1358902nathlol2Bali Sculptures (APIO15_sculpture)C++20
0 / 100
8 ms4408 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int n, a, b, ans, pf[N];
bool dp[N][N], fuck[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 >> pf[i];
        pf[i] += pf[i - 1];
    }
    for(int i = 1;i<=n;i++){
        for(int j = max(0LL, i - b);j<=i - a;j++) can[i].push_back(j);
    }
    for(int bit = 45;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] - pf[x]) >> bit) == 0 || (fuck[bit + 1] && ((pf[i] - pf[x]) >> bit) == 2)){
                        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{
            fuck[bit] = 1;
            ans += (1 << bit);
        }
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...