Submission #40736

#	Time	Username	Problem	Language	Result	Execution time	Memory
40736		bogdan10bos	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	107 ms	1192 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

int N, A, B;
int v[2005];
LL s[2005];
LL ans;
int dp1[2005];
int dp[105][105];

bool can(int b)
{
    LL pw = (1LL << b);
    if(A == 1)
    {
        dp1[0] = 0;
        for(int i = 1; i <= N; i++)
        {
            dp1[i] = N + 1;
            for(int j = 0; j < i; j++)
                if( ( (s[i] - s[j]) & (~ans) ) < pw )
                    dp1[i] = min(dp1[i], dp1[j] + 1);
        }
        return (dp1[N] <= B);
    }

    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= B; j++)
        {
            dp[i][j] = 0;
            for(int k = 0; k < i; k++)
                if( ( (s[i] - s[k]) & (~ans) ) < pw )
                    dp[i][j] |= dp[k][j - 1];
        }

    for(int i = A; i <= B; i++)
        if(dp[N][i])    return true;
    return false;
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &A, &B);
    for(int i = 1; i <= N; i++) scanf("%d", &v[i]), s[i] = s[i - 1] + v[i];

    ans = 0;
    for(int b = 41; b >= 0; b--)
        if( !can(b) )
            ans ^= (1LL << b);

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:55:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &A, &B);
                                ^
sculpture.cpp:56:75: 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("%d", &v[i]), s[i] = s[i - 1] + v[i];
                                                                           ^

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