Submission #1271940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271940		bbldrizzy	Bali Sculptures (APIO15_sculpture)	C++20	0 / 100	1 ms	648 KiB

sculpture

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

bool check(ll x, vector<ll> v) {
    vector<ll> dp(n);
    vector<ll> dp2(n, 1e9);
    dp2[0] = 1;
    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 (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++) {
        pref[i+1] = pref[i] + v[i];
    }
    // cout << check(11, v);
    // cout << "\n";
    ll pre = (1<<31)-1;
    // cout << pre << "\n";
    ll idx = 30;
    while (idx >= 0) {  
        ll cur = pre-(1<<idx);
        // cout << "cur, check: " << cur << ", " << check(cur, v) << "\n";
        if (check(cur, v)) pre = cur;
        // cout << "idx, pre: " << idx << " " << pre << "\n";
        idx--;
    }
    cout << pre;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:58:21: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   58 |     ll pre = (1<<31)-1;
      |              ~~~~~~~^~

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