Submission #96440

#	Time	Username	Problem	Language	Result	Execution time	Memory
96440		Smelskiy	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	95 ms	508 KiB

sculpture

# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_set>
# include <unordered_map>
using namespace std;


int A, B, n;
int a[2005];
int dp[2005];
bool dp2[2005][2005];

inline bool check(long long msk) {
    if (A == 1) {
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
            dp[i] = 1e9;
        for (int i = 0; i < n; ++i) {
            long long s = 0;
            for (int j = i + 1; j <= n; ++j) {
                s += a[j];
                if ((s & msk) == s) dp[j] = min(dp[j], dp[i] + 1);
            }
        }
        return (bool)(dp[n] <= B);
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= B; ++j)
            dp2[i][j] = false;
    }
    dp2[0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < B; ++j) if (dp2[i][j]) {
            long long s = 0;
            for (int k = i + 1; k <= n; ++k) {
                s += a[k];
                if ((s & msk) == s) dp2[k][j + 1] = true;
            }
        }
    }
    for (int i = A; i <= B; ++i)
        if (dp2[n][i]) return true;
    return false;
}

long long solve(int N, int AA, int BB, int ar[]) {
    A = AA;
    B = BB;
    n = N;
    for (int i = 1; i <= n; ++i)
        a[i] = ar[i - 1];
    long long res = (1ll << 45ll) - 1ll;
    for (int i = 44; i >= 0; --i) {
        long long cur = (res ^ (1ll << i));
        if (check(cur)) res = cur;
    }
    return res;
}

int main(int argc, const char * argv[]) {
//    freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, A, B;
    cin >> n >> A >> B;
    int ar[n];
    for (int i = 0; i < n; ++i) {
        cin >> ar[i];
    }
    cout << solve(n, A, B, ar) << endl;
    return 0;
}

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