Submission #162963

#	Time	Username	Problem	Language	Result	Execution time	Memory
162963		dantoh000	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	111 ms	504 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int memo[2005];
int memo2[105][105];
ll p[2005];
int c[2005];
int a,b;
ll ans;
const int INF = 2005;
int dp(int id){
    //printf("dp %d %lld\n",id,ans);
    if (id == n) return 0;
    if (memo[id] != -1) return memo[id];
    int cur = INF;
    for (int i = id+1; i <= n; i++){
        ll sum = p[i]-p[id];
        //printf("%lld %lld %lld\n",sum,ans,sum&ans);
        ll k = sum&ans;
        if (k == 0ll){
            cur = min(cur,dp(i)+1);
        }
    }
    return memo[id] = cur;
}
int dp(int id, int curp){
    if (id == n && curp == 0) return true;
    if (memo2[id][curp] != -1) return memo2[id][curp];
    memo2[id][curp] = 0;
    for (int i = id+1; i <= n; i++){
        ll sum = p[i]-p[id];
        //printf("%lld %lld %lld\n",sum,ans,sum&ans);
        ll k = sum&ans;
        if (k == 0ll){
            memo2[id][curp] |= dp(i,curp-1);
        }
    }
    return memo2[id][curp];
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    p[0] = 0;
    for (int i = 1; i <= n; i++){
        scanf("%d",&c[i]);
        p[i] = p[i-1] + c[i];
    }
    if (a == 1){
        ans = 0;
        for (int i = 40; i >= 0; i--){
            memset(memo,-1,sizeof(memo));
            ans += (1ll<<i);
            dp(0);
            for (int i = 0; i < n; i++){
                //printf("%d ",memo[i]);
            }
            //printf("\n");
            //printf("if want to split to %lld, need %d\n",(1ll<<41)-1-ans,dp(0));
            if (dp(0) > b){
                ans -= (1ll<<i);
            }
        }
        printf("%lld ",(1ll<<41)-1-ans);
    }
    else{
        ans = 0;
        for (int i = 40; i >= 0; i--){
            memset(memo2,-1,sizeof(memo2));
            ans += (1ll<<i);
            bool can = false;
            for (int k = a; k <= b; k++) {
                //printf("%d ",dp(0,k));
                can |= dp(0,k);
            }
            //printf(" tested %lld\n",ans);
            if (can){
                //printf("can split to %lld\n",ans);
            }
            else{
                ans -= (1ll<<i);
            }
        }
        printf("%lld ",(1ll<<41)-1-ans);
    }



}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:42: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:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c[i]);
         ~~~~~^~~~~~~~~~~~

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