Submission #908243

#	Time	Username	Problem	Language	Result	Execution time	Memory
908243		treap_enjoyer	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	111 ms	856 KiB

sculpture

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define all(x) x.begin(), x.end()
#define ld long double
#define pii pair<int, int>

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
int n, a, b;
vector<ll> ar;
int try1(ll x){
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        ll csum = ar[i];
        for(int j = i - 1; j >= 0; j--){
            if((csum | x) == x){
                dp[i] = min(dp[i], dp[j] + 1);
            }
            csum += ar[j];
        }
    }
    return dp[n];
}
int try2(ll x){
    vector<vector<int> > dp(b + 1, vector<int>(n + 1, 0));
    dp[0][0] = 1;
    for(int i = 1; i <= b; i++){
        for(int j = 1; j <= n; j++){
            ll csum = ar[j];
            for(int k = j - 1; k >= 0; k--){
                if((csum | x) == x){
                    dp[i][j] |= dp[i - 1][k];
                }
                csum += ar[k];
            }
        }
    }
    int ans = 0;
    for(int i = a; i <= b; i++) ans |= dp[i][n];
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> a >> b;
    ar.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> ar[i];
    }
    if(a == 1){
        ll cur = (1ll << 50) - 1;
        for(int i = 49; i >= 0; i--){
            cur ^= (1ll << i);
            if(try1(cur) > b) cur ^= (1ll << i);
        }
        cout << cur;
        return 0;
    }
    else{
        ll cur = (1ll << 50) - 1;
        for(int i = 49; i >= 0; i--){
            cur ^= (1ll << i);
            if(!try2(cur)){
                cur ^= (1ll << i);
                if(!try2(cur)){
                    cout << "-1";
                    return 0;
                }
            }
        }
        cout << cur;
    }
}

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