Submission #223654

#	Time	Username	Problem	Language	Result	Execution time	Memory
223654		MODDI	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	107 ms	4608 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