Submission #601191

#	Time	Username	Problem	Language	Result	Execution time	Memory
601191		ace5	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	83 ms	460 KiB

sculpture

#include <bits/stdc++.h>
#include <random>
#include <ext/rope>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int maxn = 2000;
const int maxa = 1e9;
const int64_t maxs = 41;

int main()
{
    int64_t n,A,B;
    cin >> n >> A >> B;
    int64_t y[n];
    for(int i = 0;i < n;++i)
    {
        cin >> y[i];
    }
    if(n <= 100)
    {
        int64_t mask = ((1ll<<42)-1);
        for(int64_t b = maxs;b >= 0;--b)
        {
            mask &= (~(1ll<<b));
            int64_t dp[n+1][n+1];
            for(int j = 0;j <= n;++j)
            {
                if(j == 0)
                    dp[n][j] = 1;
                else
                    dp[n][j] = 0;
            }
            for(int i = n-1;i >= 0;--i)
            {
                for(int j = 0;j <= n;++j)
                    dp[i][j] = 0;
                int64_t tsum = 0;
                for(int j = i;j < n;++j)
                {
                    tsum += y[j];
                   // cout << tsum << ' ' << mask << ' ' << (tsum&mask) << "\n";
                    if((tsum&mask) == tsum)
                    {
                        for(int k= 0;k <= n;++k)
                        {
                            if(dp[j+1][k] == 1)
                                dp[i][k+1] = 1;
                        }
                    }
                }
            }
            int yes = 0;
            for(int i =A;i <= B;++i)
            {
                if(dp[0][i])
                    yes = 1;
            }
            if(!yes)
            {
                mask |= (1ll<<b);
            }
        }
        cout << mask;
        return 0;
    }
    else
    {
        int64_t mask = ((1ll<<42)-1);
        for(int64_t b = maxs;b >= 0;--b)
        {
            mask &= (~(1ll<<b));
            int64_t dp[n+1];
            dp[n] = 0;
            for(int i = n-1;i >= 0;--i)
            {
                dp[i] = n+1;
                int64_t tsum = 0;
                for(int j = i;j < n;++j)
                {
                    tsum += y[j];
                    if((tsum&mask) == tsum)
                    {
                        dp[i] = min(dp[i],dp[j+1]+1);
                    }
                }
            }
            if(dp[0] > B)
            {
                mask |= (1ll<<b);
            }
        }
        cout << mask;
        return 0;
    }
}

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