Submission #609691

#	Time	Username	Problem	Language	Result	Execution time	Memory
609691		krit3379	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	1 ms	340 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 2005

long long arr[N],qs[N][N],dp[N],now,ans;
bitset<100> bit;
bitset<N> ok[N];

int main(){
    int n,a,b,i,j,k;
    scanf("%d %d %d",&n,&a,&b);
    for(i=1;i<=n;i++)scanf("%lld",&arr[i]),arr[i]+=arr[i-1];
    for(i=1;i<=n;i++)for(j=i;j<=n;j++)qs[i][j]=arr[j]-arr[i-1];
    if(a==1){
        for(i=50;i>=0;i--){
            now=0;
            for(j=50;j>i;j--)now=bit[j]*(1ll<<j);
            for(j=i-1;j>=0;j--)now+=1ll<<j;
            for(j=1;j<=n;j++)for(k=j;k<=n;k++)ok[j][k]=((qs[j][k]|now)==now);
            for(j=1;j<=n;j++){
                dp[j]=ok[1][j]?1:1e9;
                for(k=1;k<j;k++)if(ok[k+1][j])dp[j]=min(dp[j],dp[k]+1);
            }
            if(dp[n]>b)bit[i]=true;
        }
        for(i=0;i<50;i++)if(bit[i])ans+=1ll<<i;
        printf("%lld",ans);
    }
    return 0;
}

Compilation message (stderr)

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

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