Submission #232483

#	Time	Username	Problem	Language	Result	Execution time	Memory
232483		balbit	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	43 ms	512 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()

#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif // BALBIT

#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define pb push_back

bool dp[102][102];

signed main(){
    IOS();
    int n; cin>>n;
    vector<ll> ps(n+1);
    int A, B; cin>>A>>B;
    for (int i = 0; i<n; ++i) {
        cin>>ps[i+1]; ps[i+1] += ps[i];
    }
    ll BAD = 0;
    ll ANS = 0;
    for (int bt = 40; bt >= 0; -- bt) {
        BAD |= (1ll<<bt);
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        bool ok = 0;
        for (int i = 1; i<=n; ++i) {
            for (int k = 1; k <=n; ++k) {
                for (int j = 0; j<i; ++j) {
                    if (((ps[i] - ps[j]) & BAD) == 0 && dp[j][k-1]) {
                        dp[i][k] =1; break;
                    }
                }
                if (dp[i][k] && i == n && k >= A && k <= B) {
                    ok = 1; break;
                }
            }
        }
        if (!ok) {
            BAD ^= (1ll<<bt);
            ANS |= (1ll<<bt);
        }
    }
    cout<<ANS<<endl;
}
/*
6 1 3
8 1 2 1 5 4
*/

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