Submission #328622

#	Time	Username	Problem	Language	Result	Execution time	Memory
328622		Mahdi_Shokoufi	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	219 ms	32144 KiB

sculpture

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

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

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())

const int N = 2010;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 10;

ll y[N], n, a, b;
ll dp1[N][N];
ll dp2[N];

bool check1(ll x){
    for (int i = 0; i < N; i ++)
        for (int  j = 0; j < N; j ++)
            dp1[i][j] = 0;
    dp1[0][0] = 1;
    for (int i = 1; i <= n; i ++){
        ll s = 0;
        for (int j = i; j; j --){
            s += y[j];
            if ((s | x) == x){
                for (int k = 1; k <= n; k ++)
                    dp1[i][k] |= dp1[j - 1][k - 1];
            }
        }
    }
    for (int i = a; i <= b; i ++)
        if (dp1[n][i])
            return true;
    return false;
}

bool check2(ll x){
    for (int i = 0; i < N; i ++)
        dp2[i] = N;
    dp2[0] = 0;
    for (int i = 1; i <= n; i ++){
        ll s = 0;
        for (int j = i; j; j --){
            s += y[j];
            if ((s | x) == x){
                dp2[i] = min(dp2[i], dp2[j - 1] + 1);
            }
        }
    }
    return dp2[n] <= b;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (ll i = 1; i <= n; i ++)
        cin >> y[i];
    if (n <= 100){
        ll ans = (1LL << 40) - 1;
        for (ll i = 39; i >= 0; i --)
            if (check1(ans ^ (1LL << i)))
                ans ^= (1LL << i);
        cout << ans;
        return 0;
    }
    ll ans = (1LL << 45) - 1;
    for (ll i = 44; i >= 0; i --)
        if (check2(ans ^ (1LL << i)))
            ans ^= (1LL << i);
    cout << ans;
    return 0;
}

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