Submission #879541

#	Time	Username	Problem	Language	Result	Execution time	Memory
879541		Shayan86	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	47 ms	608 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll L = 41;
const ll M = 107;
const ll N = 2e3 + 50;
const ll inf = 1e9 + 7;

ll n, A, B, arr[N], ps[N], dist[N];

bool isok[M][M];

void solve1(){
    ll res = 0;
    for(int i = L-1; i >= 0; i--){
        for(int j = 0; j < M; j++) for(int k = 0; k < M; k++) isok[j][k] = 0;
        isok[0][0] = 1;

        for(int j = 1; j <= n; j++){
            for(int l = 0; l < j; l++){
                ll a = (ps[j] - ps[l]) >> i;
                ll b = res >> i; b = ~b;
                if(a & b) continue;

                for(int k = 1; k <= B; k++) isok[j][k] |= isok[l][k-1];
            }
        }

        bool ch = false;
        for(int j = A; j <= B; j++) ch |= isok[n][j];

        if(!ch) res |= (1ll << i);
    }
    cout << res;
}

void solve2(){
    ll res = 0;
    for(int i = L-1; i >= 0; i--){
        dist[0] = 0;
        for(int j = 1; j <= n; j++) dist[j] = inf;
        for(int j = 1; j <= n; j++){
            for(int l = 0; l < j; l++){
                ll a = (ps[j] - ps[l]) >> i;
                ll b = res >> i; b = ~b;
                if(a & b) continue;
                dist[j] = min(dist[j], dist[l]+1);
            }
        }
        if(dist[n] > B) res |= (1ll << i);
    }
    cout << res;
}

int main(){
    fast_io;

    cin >> n >> A >> B;

    for(int i = 1; i <= n; i++){
        cin >> arr[i]; ps[i] = ps[i-1] + arr[i];
    }

    if(A == 1) solve2();
    else solve1();

}

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