Submission #1014324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014324		aufan	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	124 ms	604 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inf = 1e9;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, a, b;
        cin >> n >> a >> b;

        vector<int> v(n + 1);
        for (int i = 1; i <= n; i++) cin >> v[i];

        vector<int> p(n + 1);
        for (int i = 1; i <= n; i++) p[i] = p[i - 1] + v[i];

        int ans = (1ll << 60) - 1;
        for (int j = 59; j >= 0; j--) {
                ans -= (1ll << j);

                vector<pair<int, int>> dp(n + 1, {inf, -inf}); // mn - mx
                dp[0] = {0, 0};
                for (int i = 1; i <= n; i++) {
                        for (int k = 0; k < i; k++) {
                                int sum = p[i] - p[k];
                                if ((sum | ans) == ans && dp[k].fi != inf) {
                                        dp[i].fi = min(dp[i].fi, dp[k].fi + 1);
                                        dp[i].se = max(dp[i].se, dp[k].se + 1);
                                }
                        }
                }

                if (dp[n].fi == inf || max(a, dp[n].fi) > min(b, dp[n].se)) {
                        ans += (1ll << j);
                }
        }

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

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