Submission #1212077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212077		A_M_Namdar	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	136 ms	504 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e9, N = 2e3 + 10;
long long n, a, b, c[N], v[N];

void input() {
	cin >> n >> a >> b;
    for (long long i = 1; i <= n; i++) 
		cin >> c[i];
}

void solve() {
    long long ans = (1LL << 60) - 1;
    for (long long i = 1; i <= n; i++) 
		v[i] = v[i - 1] + c[i];
    for (long long j = 59; j >= 0; j--){
        ans -= (1LL << j);
        vector<pair<long long,long long>> dp(n + 1, {inf, -inf});
        dp[0] = {0, 0};
        for (long long i = 1; i <= n; i++){
            for (long long k = 0; k < i; k++){
                long long sum = v[i] - v[k];
                if ((ans | sum) == ans && dp[k].first != inf){
                    dp[i].first = min(dp[i].first, dp[k].first + 1);
                    dp[i].second = max(dp[i].second, dp[k].second + 1);
                }
            }
        }
        if (dp[n].first == inf || max(a, dp[n].first) > min(b, dp[n].second)) 
			ans += (1LL << j);
    }
    cout << ans;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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