Submission #885167

#	Time	Username	Problem	Language	Result	Execution time	Memory
885167		AnhPham	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	19 ms	4952 KiB

sculpture

#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long // maybe tle?
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;

TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

TcT, class S>   istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second;        }
TcT, class S>   ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }

void solve();

int32_t main() {
    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

const int N = 2002;

int n, a, b;
int y[N];

namespace sub1 {
    int ans = INF64;

    void Try(int k, int groups, int sum, int sum_or) {
        if (k > n) {
            if (a <= groups && groups <= b)
                minimize(ans, sum_or | sum);

            return;
        }

        Try(k + 1, groups, sum + y[k], sum_or);
        Try(k + 1, groups + 1, y[k], sum_or | sum);
    }
    
    void solve() {
        Try(2, 1, y[1], 0);

        cout << ans << '\n';
    }
}

namespace sub2 {
    bool dp[55][22][505];

    void solve() {
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int groups = 0; groups <= b; ++groups)
                for (int sum_or = 0; sum_or <= 500; ++sum_or) {
                    int sum = 0;
                    for (int j = i; j >= 1; --j)
                        dp[i][groups + 1][sum_or | (sum += y[j])] |= dp[j - 1][groups][sum_or];
                }

        int ans = INF64;
        for (int groups = a; groups <= b; ++groups)
            for (int sum_or = 0; sum_or <= 500; ++sum_or)
                if (dp[n][groups][sum_or])
                    minimize(ans, sum_or);

        cout << ans << '\n';
    }
}

namespace sub3 {
    int dp[101][2002];

    void solve() {
        memset(dp, 0x3f, sizeof (dp));

        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int sum_or = 0; sum_or <= 2000; ++sum_or) {
                int sum = 0;
                for (int j = i; j >= 1; --j)
                    minimize(dp[i][sum_or | (sum += y[j])], dp[j - 1][sum_or] + 1);
            }

        int ans = INF64;
        for (int sum_or = 0; sum_or <= 2000; ++sum_or)
            if (dp[n][sum_or] <= b)
                minimize(ans, sum_or);
        
        cout << ans << '\n';
    }
}

namespace sub4 {
    bool dp[N][N];

    bool can(int mask) {
        memset(dp, 0, sizeof (dp));

        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            memset(dp[i], 0, sizeof (dp[i]));

            int sum = 0;
            for (int j = i; j >= 1; --j) {
                sum += y[j];
                if ((~mask & sum) == 0)
                    for (int groups = 1; groups <= b; ++groups)
                        dp[i][groups] |= dp[j - 1][groups - 1];
            }
        }

        for (int groups = a; groups <= b; ++groups)
            if (dp[n][groups])
                return 1;
        
        return 0;
    }

    void solve() {
        int ans = (1ll << 61) - 1;
        for (int bit = 60; bit >= 0; --bit)
            if (can(ans ^ (1ll << bit)))
                ans ^= (1ll << bit);
        
        cout << ans << '\n';
    }
}

namespace sub5 {
    int dp[N];

    bool can(int mask) {
        memset(dp, 0x3f, sizeof (dp));

        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int sum = 0;
            for (int j = i; j >= 1; --j) {
                sum += y[j];
                if ((~mask & sum) == 0)
                    minimize(dp[i], dp[j] + 1);
            }
        }

        return dp[n] <= b;
    }

    void solve() {
        int ans = (1ll << 61) - 1;
        for (int bit = 60; bit >= 0; --bit)
            if (can(ans ^ (1ll << bit)))
                ans ^= (1ll << bit);
        
        cout << ans << '\n';
    }
}

void solve() {
    cin >> n >> a >> b;

    for (int i = 1; i <= n; ++i)
        cin >> y[i];
    
    if (n <= 20)
        sub1 :: solve();
    else if (n <= 50)
        sub2 :: solve();
    else if (n <= 100 && a == 1 && *max_element(y + 1, y + 1 + n) <= 20)
        sub3 :: solve();
    else if (n <= 100)
        sub4 :: solve();
    else if (n <= 2000 && a == 1)
        sub5 :: solve();
}

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