Submission #146451

#	Time	Username	Problem	Language	Result	Execution time	Memory
146451		arnold518	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	361 ms	32120 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int N, A, B;
ll Y[MAXN+10], ans=0, dp1[MAXN+10], dp2[MAXN+10][MAXN+10];

int main()
{
    int i, j, k, p;

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

    ans=(1ll<<46)-1;
    if(A==1)
    {
        for(i=45; i>=0; i--)
        {
            ll now=1ll<<i;
            ans^=now;
            for(j=1; j<=N; j++) dp1[j]=987654321; dp1[0]=0;
            for(j=1; j<=N; j++) for(k=0; k<j; k++) if((ans|(Y[j]-Y[k]))==ans) dp1[j]=min(dp1[j], dp1[k]+1);
            if(dp1[N]>B) ans|=now;
        }
    }
    else
    {
        for(i=45; i>=0; i--)
        {
            ll now=1ll<<i;
            ans^=now;
            memset(dp2, 0, sizeof(dp2)); dp2[0][0]=1;
            for(j=1; j<=N; j++) for(k=1; k<=N; k++) for(p=0; p<j; p++) if((ans|(Y[j]-Y[p]))==ans) dp2[j][k]|=dp2[p][k-1];
            bool flag=false;
            for(j=A; j<=B; j++) flag|=dp2[N][j];
            if(!flag) ans|=now;
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:27:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(j=1; j<=N; j++) dp1[j]=987654321; dp1[0]=0;
             ^~~
sculpture.cpp:27:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             for(j=1; j<=N; j++) dp1[j]=987654321; dp1[0]=0;
                                                   ^~~
sculpture.cpp:17:10: 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:18:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &Y[i]), Y[i]+=Y[i-1];
                         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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