Submission #1098900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098900		TrinhKhanhDung	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	87 ms	856 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 2e3 + 10;

int N, A, B;
int a[MAX];

void solve(){
    cin >> N >> A >> B;
    for(int i = 1; i <= N; i++) cin >> a[i];
}

namespace subtask4{
    const int MAX = 1e3 + 10;
    const int LOG = 37;

    bitset<MAX> dp[MAX];

    void solve(){
        ll bitdel = 0;

        for(int t = LOG - 1; t >= 0; t--){
            bitdel |= MASK(t);

            dp[0][0] = true;
            for(int i = 1; i <= N; i++){
                ll cur = 0;
                for(int j = i; j <= N; j++){
                    cur += a[j];
                    if((cur & bitdel) == 0){
                        dp[j] |= dp[i - 1] << 1;
                    }
                }
            }

            bool ok = false;
            for(int i = A; i <= B; i++){
                if(dp[N][i] == true){
                    ok = true; break;
                }
            }

            if(!ok){
                bitdel ^= MASK(t);
            }

            for(int i = 1; i <= N; i++){
                dp[i].reset();
            }
        }

        cout << (MASK(LOG) - 1 - bitdel) << '\n';
    }
}

namespace subtask5{
    const int LOG = 41;

    void solve(){
        ll bitDel = 0;

        for(int t = LOG - 1; t >= 0; t--){
            bitDel |= MASK(t);

            vector<int> dp(N + 3, INF);
            dp[0] = 0;
            for(int i = 1; i <= N; i++){
                ll cur = 0;
                for(int j = i; j <= N; j++){
                    cur += a[j];
                    if((cur & bitDel) == 0){
                        minimize(dp[j], dp[i - 1] + 1);
                    }
                }
            }
            if(dp[N] > B){
                bitDel ^= MASK(t);
            }
        }

        cout << (MASK(LOG) - 1 - bitDel) << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//     freopen("btower.inp","r",stdin);
//     freopen("btower.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
        if(N <= 100) subtask4::solve();
        else
            subtask5::solve();
    }

    return 0;
}

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