제출 #41852

#제출 시각아이디문제언어결과실행 시간메모리
41852XmtosXBali Sculptures (APIO15_sculpture)C++14
100 / 100
591 ms1124 KiB
#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;
                break;
            }
        }
        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;
                break;
            }
        }
        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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...