Submission #219965

#	Time	Username	Problem	Language	Result	Execution time	Memory
219965		MKopchev	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1098 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);
    }
}
bool can(long long to_test)
{
    current=to_test;

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

    possible=0;

    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:49: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:50: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: 0 / 29