Submission #150958

#	Time	Username	Problem	Language	Result	Execution time	Memory
150958		osaaateiasavtnl	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1022 ms	4448 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
const int N = 2001, LG = 50;
int n, L, R;
int a[N];
bool dp[N][N];
bool check(int ban) {
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int j = i; j >= 1; --j) {
            sum += a[j];
            if ((sum & ban) == 0) {
                for (int k = 1; k <= n; ++k) {
                    dp[i][k] |= dp[j - 1][k - 1];
                }   
            }   
        }   
    }
    for (int i = L; i <= R; ++i) if (dp[n][i]) return 1;
    return 0;
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> L >> R;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ban = 0;
    for (int b = LG - 1; b >= 0; --b) if (check(ban + (1ll << b))) ban += 1ll << b; 
    cout << (1ll << LG) - 1 - ban << '\n';
}   

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