Submission #1358912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358912		nathlol2	Bali Sculptures (APIO15_sculpture)	C++20	0 / 100	8 ms	4412 KiB

sculpture

#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]){
                    int cc = pf[i] - pf[x];
                    if((cc >> bit) == 0){
                        dp[i][k] |= dp[x][k - 1];
                        if(k == 1) ncan[i].push_back(x);
                        continue;
                    }
                    bool f = 1;
                    for(int bb = bit;bb<=45;bb++){
                        if((cc & (1LL << bb)) && !fuck[bb]){
                            f = 0;
                            break;
                        }
                    }
                    if(f){
                        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;
}

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