Submission #162958

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

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int memo[2005];
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 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];
    }
    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);



}

Compilation message (stderr)

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

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