Submission #30877

#	Time	Username	Problem	Language	Result	Execution time	Memory
30877		Navick	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	96 ms	2052 KiB

sculpture

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <time.h>
#include <limits.h>
 
using namespace std;
 
typedef long long ll;
typedef double lf;
 
const int N_ = 2050;
 
int N, A, B;
ll S[N_];
 
ll ans;
 
bool tb1[105][105];
 
void solve1() {
    ans = 0;
    ll cur = 0;
    for(int b = 41; b >= 0; b--) {
        ll t = cur | (1ll << b);
 
        tb1[0][0] = true;
        for(int i = 1; i <= N; i++) for(int x = 1; x <= i; x++) {
            tb1[i][x] = false;
            for(int j = 0; j < i; j++) {
                ll s = S[i] - S[j];
                if((s & t) == 0) tb1[i][x] |= tb1[j][x - 1];
            }
        }
 
        bool good = false;
        for(int x = A; x <= B; x++) good |= tb1[N][x];
 
        if(good) {
            cur = t;
        }else {
            ans += 1ll << b;
        }
    }
}
 
int tb2[N_];
 
void solve2() {
    ans = 0;
    ll cur = 0;
    for(int b = 41; b >= 0; b--) {
        ll t = cur | (1ll << b);
 
        for(int i = 1; i <= N; i++) {
            tb2[i] = (int)1e6;
            for(int j = 0; j < i; j++) {
                ll s = S[i] - S[j];
                if((s & t) == 0) tb2[i] = min(tb2[i], tb2[j] + 1);
            }
        }
 
        //printf("%lld %lld %d\n", ans, 1ll<<b, tb2[N]);
        if(tb2[N] <= B) {
            cur = t;
        }else {
            ans += 1ll << b;
        }
    }
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
 
    scanf("%d%d%d", &N, &A, &B);
    for(int i = 1; i <= N; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i-1] + x;
    }
 
    if(N <= 100) {
        solve1();
    }else {
        solve2();
    }
 
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:78:32: 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:80:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                               ^

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