제출 #1332158

#제출 시각아이디문제언어결과실행 시간메모리
1332158dymeztkyBali Sculptures (APIO15_sculpture)C++20
100 / 100
148 ms484 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define dymeztky ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define calc(a,x) accumulate(a.begin()+x,a.end(),0LL)
#define ub(a,x) upper_bound(a.begin(), a.end(), x)
#define lb(a,x) lower_bound(a.begin(), a.end(), x)
#define rep(m, n, k) for(int m = n; m <= k; m++)
#define rev(m, n, k) for(int m = n; m >= k; m--)
#define mnel(a) min_element(a.begin(), a.end())
#define mxel(a) max_element(a.begin(), a.end())
#define all(a,x) a.begin()+x, a.end()
#define iii tuple<int,int,int>
#define vvi vector<vector<int>>
#define pc __builtin_popcount
#define prq priority_queue
#define pii pair<int,int>
#define mii map<int,int>
#define sz size() 
#define pb push_back
#define fi first
#define se second
#define endl "\n"

bool debug = false;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, L, R;
vector<int> a, pre;

bool valid(int mask) {
    if(L != 1) {
        vector<bitset<2005>> dp(n+1);
        dp[0][0] = 1;

        rep(i,1,n) {
            rep(j,0,i-1) {
                if(((pre[i] - pre[j]) | mask) == mask) {
                    dp[i] |= (dp[j] << 1);
                }
            }
        }

        rep(i,L,R) if(dp[n][i]) return true;
        return false;
        
    } else { // edge case subtask 5 lol
        vector<int> dp(n+1,inf);
        dp[0] = 0;

        rep(i,1,n) {
            rep(j,0,i-1) {
                if(((pre[i] - pre[j]) | mask) == mask && dp[j] != inf) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n] <= R;
    }
}

void solve() {
    cin >> n >> L >> R;
    a.resize(n+1);
    pre.resize(n+1,0);

    rep(i,1,n) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    int ans = 0;
    rev(i,60,0) {
        if(!valid(ans | ((1LL << i) - 1))) ans |= (1LL << i);
    }

    cout << ans;
}

int32_t main() {
    dymeztky;

    int t = 1;
    rep(tc,1,t) {
        if(debug) cerr << "--- TC " << tc << " ---" << endl;
        solve(); 
        cout << endl; 
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...