Submission #219968

#	Time	Username	Problem	Language	Result	Execution time	Memory
219968		MKopchev	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	105 ms	4600 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e3+42;
int n,a,b,inp[nmax];
long long pref[nmax];

long long current;

bool possible;

bool been[nmax][nmax];

void dfs(int groups,int last_end)
{
    if(possible)return;
    if(groups>b)return;

    if(last_end==n)
    {
        if(groups>=a)possible=1;
        return;
    }

    if(been[groups][last_end])return;
    been[groups][last_end]=1;

    if(((pref[n]-pref[last_end])&current)==(pref[n]-pref[last_end]))dfs(groups+1,n);

    for(int j=last_end+1;j<n;j++)
    {
        long long sum=pref[j]-pref[last_end];
        if((current&sum)==sum)dfs(groups+1,j);
    }
}

int dp[nmax];
void special()
{
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1e9;
        for(int j=i;j>=1;j--)
        {
            long long sum=pref[i]-pref[j-1];
            if((sum&current)==sum)dp[i]=min(dp[i],dp[j-1]+1);
        }
    }

    //for(int i=1;i<=n;i++)cout<<dp[i]<<" ";cout<<endl;

    possible=(dp[n]<=b);
}
bool can(long long to_test)
{
    current=to_test;

    memset(been,0,sizeof(been));

    possible=0;

    if(a==1)special();
    else dfs(0,0);

    return possible;
}
int main()
{
    scanf("%i%i%i",&n,&a,&b);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+inp[i];

    long long output=(1LL<<41)-1;

    for(int i=40;i>=0;i--)
        if(can(output-(1LL<<i)))output=output-(1LL<<i);

    printf("%lld\n",output);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&a,&b);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sculpture.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

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