Submission #1180742

#TimeUsernameProblemLanguageResultExecution timeMemory
1180742petezaBali Sculptures (APIO15_sculpture)C++20
100 / 100
101 ms23176 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;

int n, l, r;
ll sums[2005][2005];
pair<int, int> dp[2005];

bool inter(int l, int r, int L, int R) {
    return max(l, L) <= min(r, R);
}

int main() {
    cin >> n >> l >> r;
    for(int i=1;i<=n;i++) {
        cin >> sums[i][i];
        for(int j=i-1;j>=1;j--) {
            sums[j][i] = sums[j+1][i] + sums[j][j];
        }
    }
    ll ans = 0, bruh = -1;
    for(int i=46;i>=0;i--) {
        //run dp
        dp[0]={0, 0};
        for(int i=1;i<=n;i++) dp[i] = {inf, -inf};
        bruh ^= (1ll << i);
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<=n;j++) {
                if((bruh | sums[i+1][j])==bruh){
                    //valid af
                    dp[j].first = min(dp[j].first, dp[i].first+1);
                    dp[j].second = max(dp[j].second, dp[i].second+1);
                }
            }
        }
        if(!inter(l, r, dp[n].first, dp[n].second)) {
            ans ^= (1ll<<i);
            bruh ^= (1ll << i);
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...