Submission #1271944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271944		bbldrizzy	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	63 ms	724 KiB

sculpture

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <set>
#include <random>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const ll MOD = 1e9+7;
const ll inf = 4*1e18;
const ll MX = 5*1e5+5;
ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {1, 0, -1, 0};
ll n, a, b;
vector<ll> pref;

bool check(ll x, vector<ll> v) {
    vector<ll> dp(n, -1e9);
    vector<ll> dp2(n, 1e9);
    dp2[0] = ((x|v[0]) == x)?1:1e9;
    dp[0] = ((x|v[0]) == x)?1:-1e9;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            ll vl = pref[j+1]-pref[i];
            // cout << "i, j, vl: " << i << " " << j << " " << vl << "\n";
            if ((x|vl) == x) {
                // cout << "updating " << j << "\n";
                dp[j] = max(dp[j], (i==0?0:dp[i-1])+1);
                dp2[j] = min(dp2[j], (i==0?(ll)0:dp2[i-1])+1);
                // cout << "j: " << j << " dp: " << dp[j] << " dp2: " << dp2[j] << "\n";
            }
        }
    }
    // cout << "dp: ";
    // for (ll v : dp) cout << v << " ";
    // cout << "\n";
    // cout << "dp2: ";
    // for (ll v : dp2) cout << v << " ";
    // cout << "\n";
    return (dp[n-1] >= a && dp2[n-1] <= b);
}

int main() {
    // freopen("input.in", "r", stdin);
    // freopen("lifeguards.in", "r", stdin);
    // freopen("lifeguards.out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> a >> b;
    vector<ll> v(n);
    pref.resize(n+1);
    for (ll i = 0; i < n; i++) cin >> v[i];
    for (ll i = 0; i < n; i++) {
        pref[i+1] = pref[i] + v[i];
    }
    // cout << check(9, v);
    // cout << "\n";
    ll pre = (1LL<<47)-1;
    // cout << pre << "\n";
    ll idx = 46;
    while (idx >= 0) {  
        ll cur = pre-(1LL<<idx);
        // cout << "cur, check: " << cur << ", " << check(cur, v) << "\n";
        if (check(cur, v)) pre = cur;
        // cout << "idx, pre: " << idx << " " << pre << "\n";
        idx--;
    }
    cout << pre;
}

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