Submission #1180742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180742		peteza	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	101 ms	23176 KiB

sculpture

#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;
}

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