Submission #249658

#	Time	Username	Problem	Language	Result	Execution time	Memory
249658		receed	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	235 ms	780 KiB

sculpture

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1001;
int dp[N][N], d2[N];
ll ps[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    rep(i, n) {
        cin >> ps[i + 1];
        ps[i + 1] += ps[i];
    }
    ll ans = 0;
    if (a > 1) 
        for (int i = 41; i >= 0; i--) {
            ans += (1ll << i) - 1;
            rep(j, b + 1)
                rep(k, n + 1)
                    dp[j][k] = 0;
            dp[0][0] = 1;
            rep(j, b)
                rep(k, n)
                    rep(l, k + 1) {
                        ll x = ps[k + 1] - ps[l];
                        if (dp[j][l] && (ans & x) == x) {
                            dp[j + 1][k + 1] = 1;
                            break;
                        }
                    }
            int f = 0;
            for (int j = a; j <= b; j++)
                if (dp[j][n])
                    f = 1;
            ans -= (1ll << i) - 1;
            if (!f)
                ans += (1ll << i);
        }
    else
        for (int i = 41; i >= 0; i--) {
            ans += (1ll << i) - 1;
            rep(j, n)
                d2[j + 1] = n + 1;
            rep(k, n)
                rep(l, k + 1) {
                    ll x = ps[k + 1] - ps[l];
                    if ((ans & x) == x)
                        d2[k + 1] = min(d2[k + 1], d2[l] + 1);
                }
            ans -= (1ll << i) - 1;
            if (d2[n] > b)
                ans += (1ll << i);
        }
    cout << ans;
}

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