제출 #1210043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210043		anfi	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	131 ms	476 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9;

signed main(){
    int n,a,b; cin >> n >> a >> b;
    long long ans = (1LL << 60)-1;
    vector<int> c(n+1),v(n+1, 0);
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) v[i] = v[i-1]+c[i];
    for(int j = 59; j >= 0; j--){
        ans -= (1LL << j);
        vector<pair<int,int>> dp(n+1, {inf, -inf});
        dp[0] = {0, 0};
        for(int i = 1; i <= n; i++){
            for(int k = 0; k < i; k++){
                int sum = v[i]-v[k];
                if((ans | sum) == 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;
}

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