제출 #232579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232579		balbit	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	93 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 pii pair<int, int>
#define f first
#define s second

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

bool dp[102][102];
int D[2005];

signed main(){
    IOS();
    int n; cin>>n;
    vector<ll> ps(n+1);
    int A, B; cin>>A>>B;
    if (A!=1){
        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;
    }else{
        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 = 45; bt >= 0; -- bt) {
            BAD |= (1ll<<bt);
            memset(D, 0x3f, sizeof D);
            D[0] = 0;
            bool ok = 0;
            for (int i = 1; i<=n; ++i) {
                for (int j = 0; j<i; ++j) {
                    if (((ps[i] - ps[j]) & BAD) == 0) {
                        D[i] = min(D[i], D[j]+1);
                    }
                }
                if (D[i] <=B && i == n) {
                    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: 29 / 29