Submission #1134850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134850		Roumak77	Bali Sculptures (APIO15_sculpture)	C++20	21 / 100	15 ms	4168 KiB

sculpture

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;
ll n, a, b;
ll curr_MIN = 1E18;

void recur(ll idx, vector<ll> &list_n, vector<ll> &pref, ll val, ll curr){

    if(curr > b){
        return;
    }
    if(val >= curr_MIN){
        return;
    }

    for(ll i = idx; i < n - 1; i++){
        ll new_val = pref[i + 1] - pref[idx];
        if(new_val >= curr_MIN){
            return;
        }
        recur(i + 1, list_n, pref, val | new_val, curr + 1);
    }

    if(curr >= a){
        ll new_val = pref[n] - pref[idx];
        curr_MIN = min(curr_MIN, new_val | val);
    }



}

/*
 *
 * Score : 25/100
 *
 */

void solve(){

    ll N = 5000;

    cin >> n >> a >> b;

    vector<ll> list_n(n, 0);
    vector<ll> prefix(n + 1, 0);

    vector<vector<ll>> dp(n, vector<ll>(N, -1));
    for(ll i = 0; i < n; i++){
        cin >> list_n[i];
        prefix[i + 1] = prefix[i] + list_n[i];
        //dp[i][0][0] = true;
    }

    for(ll i = 0; i < n; i++){
        if(i == 0){
            dp[0][list_n[i]] = 1;
            continue;
        }
        dp[i][prefix[i + 1]] = 1;
        for(ll j = 0; j < i; j++){
            for(ll k = 0; k < N; k++){
                if(dp[j][k] != -1){
                    ll new_val = prefix[i + 1] - prefix[j + 1];
                    if(dp[i][new_val | k] == -1){
                        dp[i][new_val | k] = dp[j][k] + 1;
                    }else{
                        dp[i][new_val | k] = min(dp[j][k] + 1, dp[i][new_val | k]);
                    }
                }
            }
        }

    }
    ll k = 0;
    for(ll i : dp[n - 1]){
        if(i != -1 && i <= b){
           cout << k << endl;
           return;
        }
        k++;
    }

}

bool single = true;

signed main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}

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