Submission #162971

#	Time	Username	Problem	Language	Result	Execution time	Memory
162971		dantoh000	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	103 ms	508 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a,b;
int memo[2005];
int memo2[105][105];
ll p[2005];
int c[2005];
ll ans;
const int INF = 2005;
int dp(int id){
    if (id == n) return 0;
    if (memo[id] != -1) return memo[id];
    memo[id] = INF;
    for (int i = id+1; i <= n; i++){
        if ((ll)((p[i]-p[id])&ans) == 0){
            memo[id] = min(memo[id],dp(i)+1);
        }
    }
    return memo[id];
}
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++){
        if ((ll)((p[i]-p[id])&ans) == 0){
            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);
            if (dp(0) > b){
                ans -= (1ll<<i);
            }
        }
        printf("%lld ",(1ll<<41)-1-ans);
    }
    else{
        ans = 0;
        for (int i = 36; i >= 0; i--){
            memset(memo2,-1,sizeof(memo2));
            ans += (1ll<<i);
            bool can = false;
            for (int k = a; k <= b; k++) {
                can |= dp(0,k);
            }
            if (!can){
                ans -= (1ll<<i);
            }
        }
        printf("%lld ",(1ll<<37)-1-ans);
    }
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:34: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:37: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