Submission #41849

#	Time	Username	Problem	Language	Result	Execution time	Memory
41849		XmtosX	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	1072 ms	1684 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
int n,a,b;
long long y[2003],ans,o,memo1[2003];
bool memo[102][102],vis[102][102];
bool dp (int pos,int cnt)
{
    if (pos==n)
    {
        if (cnt<=a&&cnt>=b)
            return 1;
        return 0;
    }
    if (vis[pos][cnt])
        return memo[pos][cnt];
    vis[pos][cnt]=true;
    long long sum=0;
    for (int i=pos;i<n;i++)
    {
        sum+=y[i];
        bool flag=false;
        for (long long j=40;(1LL<<j)>=o;j--)
        {
            if ((sum&(1LL<<j))>((ans&(1LL<<j))))
                flag=true;
        }
        if (!flag)
            memo[pos][cnt]|=dp(i+1,cnt+1);
    }
    return memo[pos][cnt];
}
long long dp1 (int pos)
{
    if (pos==n)
        return 0;
    if (memo1[pos]!=-1)
        return memo1[pos];
    memo1[pos]=1e9;
    long long sum=0;
    for (int i=pos;i<n;i++)
    {
        sum+=y[i];
        bool flag=false;
        for (long long j=40;(1LL<<j)>=o;j--)
        {
            if ((sum&(1LL<<j))>((ans&(1LL<<j))))
                flag=true;
        }
        if (!flag)
            memo1[pos]=min(memo1[pos],dp1(i+1)+1);
    }
    return memo1[pos];
}
int main()
{
    cin >>n>>a>>b;
    for (int i=0;i<n;i++)
        cin >>y[i];
    if (a==1)
    {
        for (long long i=40;i>=0;i--)
        {
            memset(memo1,-1,sizeof memo1);
            o=(1LL<<i);
            if (dp1(0)>b)
                ans|=o;
        }
    }
    else
    {
        for (long long i=40;i>=0;i--)
        {
            memset(vis,0,sizeof vis);
            memset(memo,0,sizeof memo);
            o=(1LL<<i);
            if (!dp(0,0))
                ans|=o;
        }
    }
    cout <<ans;
    return 0;
}

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