Submission #1085132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085132		MrPavlito	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	125 ms	32796 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
//#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 2e3+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

vector<vector<int>> sums(MAXN,vector<int>(MAXN));
int n,a,b;
int pref[MAXN];


void checka1(int& ans, int bt)
{
    vector<int> dp(MAXN, inf);
    dp[0] = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i; j>0; j--)
        {
            int trsum = pref[i]- pref[j-1];
            int p = trsum|ans;
            if(p == ans)dp[i] = min(dp[i],dp[j-1] + 1);
        }
        //cout << dp[i] << endl;
    }
    if(dp[n] > b)ans|=(1ll<<bt);
}

void checkanije1(int& ans, int bt)
{
    vector<vector<bool>> dp(MAXN, vector<bool>(MAXN, 0));
    dp[0][0] = 1;
    for(int i=1; i<=n; i++)
    {
        for(int j = 1; j<=i; j++)
        {
            for(int k=j; k<=i; k++)
            {
                int trsum = pref[i] - pref[k-1];
                int p = trsum|ans;
                if(p!=ans)continue;
                dp[i][j] = (dp[i][j]| dp[k-1][j-1]);
            }

        }
    }
    for(int i=a; i<=b; i++)if(dp[n][i])return;
    ans|= (1ll<<bt);

}


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n >> a >> b;
        vector<int>niz(n);
        for(int i=0; i<n; i++)
        {
            cin >> niz[i];
            pref[i+1] = pref[i] + niz[i];
        }
        for(int i=0; i<n; i++)for(int j=i; j<n; j++)sums[i][j] = pref[i+1]-pref[j];
        if(a == 1)
        {
            int mxbit = 50;
            int rez = (1ll<<(mxbit+1))-1;
            for(int i=mxbit; i>=0; i--)
            {
                rez ^= (1ll<<i);
                checka1(rez, i);
            }
            cout << rez << endl;
        }
        else
        {
            int mxbit = 50;
            int rez = (1ll<<(mxbit+1))-1;
            for(int i=mxbit; i>=0; i--)
            {
                rez ^= (1ll<<i);
                checkanije1(rez, i);
            }
            cout << rez << endl;
        }



    }
}

/*
6 2 3
8 1 2 1 5 4
*/

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