Submission #20157

#	Time	Username	Problem	Language	Result	Execution time	Memory
20157		murat	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	371 ms	34648 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define endl '\n'
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define mp make_pair
#define nd second
#define st first
#define type(x) __typeof(x.begin())

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int n, a, b, dp[N], dp2[105][105], aa[N], can[2001][2001], temp[2001][2001];
ll pre[2001], ans;

int f1() {
    ROF(i, n, 1) {
        dp[i] = inf;
        FOR(j, i, n)
            if(can[i][j])
                dp[i] = min(dp[i], dp[j + 1] + 1);
    }
    return dp[1] <= b;
}

int f2() {
    dp2[n + 1][0] = 1;
    ROF(i, n, 1) {
        FOR(k, 0, b) {
            dp2[i][k+1] = 0;
            FOR(j, i, n)
                if(can[i][j] && dp2[j+1][k]) {
                    dp2[i][k+1] = 1;
                    break;
                }
        }
    }
    FOR(i, a, b)
        if(dp2[1][i])
            return 1;
    return 0;
}

int main() {

    scanf("%d %d %d", &n, &a, &b);

    int last = log2(1000000000LL * n);

    FOR(i, 1, n) {
        scanf("%d", &aa[i]);
        pre[i] = aa[i] + pre[i-1];
    }

    FOR(i, 1, n)
        FOR(j, i, n)
            can[i][j] = 1;

    ROF(i, last, 0) {
        ll cur = (1ll << (ll) i);
        FOR(i, 1, n)
            FOR(j, i, n) {
                temp[i][j] = can[i][j];
                if(can[i][j] && !((pre[j] - pre[i - 1]) & cur))
                    can[i][j] = 1;
                else can[i][j] = 0;
            }
        if(a == 1 && f1()) continue;
        if(a != 1 && f2()) continue;
        ans += cur;
        FOR(i, 1, n)
            FOR(j, i, n)
                can[i][j] = temp[i][j];
    }

    cout << ans << endl;

    return 0;
}

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