Submission #435225

#	Time	Username	Problem	Language	Result	Execution time	Memory
435225		iANikzad	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	330 ms	31964 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 2e3 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int maxl = 43;
const int SQ = 400;

int n, x, y;
int ans = (1ll << maxl) - 1;

int a[maxn];
int dp[maxn], pd[maxn][maxn];

int check(int cur)
{
     memset(dp, 0, sizeof(dp)); memset(pd, 0, sizeof(pd));
     pd[0][0] = 1;

     for(int i = 1; i <= n; i++)
     {
        int sum = 0;
        dp[i] = +INF;

        for(int j = i - 1; j >= 0; j--)
        {
            sum += a[j + 1];
            if((sum | cur) != cur) continue;

            if(x == 1)
            {
                dp[i] = min(dp[i], dp[j] + 1);
                continue;
            }

            for(int k = 1; k <= i; k++)
                pd[i][k] |= pd[j][k - 1];
        }
     }

     if(x == 1) return (dp[n] <= y);
     for(int i = x; i <= y; i++) if(pd[n][i]) return 1;
     return 0;
}

int32_t main()
{
    FAST;

    cin >> n >> x >> y;

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    for(int i = maxl - 1; i >= 0; i--)
        if(check(ans ^ (1ll << i)))
            ans  ^= (1ll << i);

    cout << ans << "\n";

    return 0;
}

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