Submission #497699

#	Time	Username	Problem	Language	Result	Execution time	Memory
497699		Saacoota	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	81 ms	448 KiB

sculpture

#include    <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b)  for(int i=(a);i<(b);++i)
#define fi  first
#define se  second
#define LL  unsigned long long
#define uint unsigned int
#define pb  push_back
#define eb  emplace_back
#define bit(s,i) ((s >> i) & 1ll)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <LL , LL>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "OR"
using   namespace   std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int oo = 0x3f;
int n , p , q , a[2010] , dp[2020];
long long s[2010];
bool f[110][110];
///--------------------------
void readf() {
    cin >> n >> p >> q;
    for (int i = 1 ; i <= n ; ++i) cin >> a[i] , s[i] = s[i-1] + a[i];
}
///--------------------------
void solve1() {
    long long ans = 0;
    for (int x = 40 ; x >= 0 ; --x) {
        memset(f,false,sizeof(f));
        f[0][0] = 1;
        long long o = ans | (1ll << x);
        for (int tp = 1 ; tp <= q ; ++tp) {
            for (int i = tp ; i <= n ; ++i)
            for (int j = i ; j >= 1 ; --j) {
                long long val = s[i] - s[j-1];
                f[i][tp] |= (f[j-1][tp-1] && ((val & o) == 0));
            }
        }
        for (int tp = p ; tp <= q ; ++tp)
        if (f[n][tp]) {
            ans = o;
            break;
        }
    }
    long long res = 0;
    for (int i = 0 ; i <= 40 ; ++i)
    if (bit(ans,i) == 0) res |= (1ll << i);
    cout << res;
}
///--------------------------
void solve2() {
    long long ans = 0;
    for (int x = 40 ; x >= 0 ; --x) {
        memset(dp,0x3f,sizeof(dp));
        dp[0] = 0;
        long long o = ans | (1ll << x);
        for (int i = 1 ; i <= n ; ++i)
        for (int j = i ; j > 0 ; --j) {
            long long val = s[i] - s[j-1];
            if ((val & o) == 0) dp[i] = min(dp[i] , dp[j-1] + 1);
        }
        if (dp[n] <= q) ans = o;
    }
    long long res = 0;
    for (int i = 0 ; i <= 40 ; ++i)
    if (bit(ans,i) == 0) res |= (1ll << i);
    cout << res;
}
///--------------------------
int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   if (p != 1) solve1();
   else solve2();
}

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