Submission #444269

#	Time	Username	Problem	Language	Result	Execution time	Memory
444269		Giselus	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	120 ms	340 KiB

sculpture

#include<cstdio>
#include<algorithm>
#define S 2007
using namespace std;
typedef long long ll;

ll X[S];
ll pref[S];

int dp[S];
int dp2[107][107];

bool ok(int l, int r, ll y){
    ll p = pref[r] - pref[l-1];
    if(p & y)
        return 0;
    return 1;
}

int main(void){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    for(int i = 1; i <= n;i++){
        scanf("%lld",&X[i]);
        pref[i] = pref[i-1] + X[i];
    }
    ll current_mask = 0;
    ll odp = 0;
    dp[0] = 0;
    dp2[0][0] = 1;
    for(ll mask = ((ll)1<<40);mask > 0; mask >>= 1){
        if(a == 1){
            for(int i = 1; i <= n;i++){
                dp[i] = 1e6;
                for(int j = 0; j < i;j++){
                    if(ok(j+1,i,current_mask+mask)){
                        dp[i] = min(dp[i],dp[j] + 1);
                    }
                }
            }
            if(dp[n] <= b){
                current_mask += mask;
            }else{
                odp += mask;
            }
        }else{
            for(int i = 1; i <= n;i++){
                for(int j = 1; j <= b;j++){
                    dp2[i][j] = 0;
                    for(int k = 0; k < i;k++){
                        if(ok(k+1,i,current_mask+mask) && dp2[k][j-1]){
                            dp2[i][j] = 1;
                            break;
                        }
                    }
                }
            }
            bool jest = 0;
            for(int i = a; i <= b;i++){
                if(dp2[n][i]){
                    jest = 1;
                }
            }
            if(jest){
                current_mask += mask;
            }else{
                odp += mask;
            }
        }
    }
    printf("%lld",odp);

    return 0;
}
/*
6 1 3
8 1 2 1 5 4
*/

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d %d",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%lld",&X[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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