제출 #1346530

#제출 시각아이디문제언어결과실행 시간메모리
1346530Born_To_LaughBali Sculptures (APIO15_sculpture)C++17
100 / 100
56 ms836 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;

const int maxn = 2010;
int n, a, b;
ll pref[maxn];
namespace case1
{
    int dp[maxn][maxn]; //dp[i][j] = cut 1->i into j range and first x bit match with ans
    ll ans = 0;
    bool valid(int bit){
        dp[0][0] = 1;
        for(int i=1; i<=n; ++i){
            for(int k=0; k<=b; ++k) dp[i][k] = 0;
            for(int j=i-1; j>=0; --j){
                ll num = pref[i] - pref[j];
                if(((num >> bit) | (ans >> bit)) == (ans >> bit)){
                    for(int k=1; k<=b; ++k){
                        dp[i][k] |= dp[j][k - 1];
                    }
                }
            }
        }
        int res = 0;
        for(int i=a; i<=b; ++i) res |= dp[n][i];
        return res;
    }
    void solve(){
        for(int bit=45; bit>=0; --bit){
            if(!valid(bit)) ans |= (1ll << bit);
        }
        cout << ans << '\n';
    }
}
namespace case2
{
    bool check(){
        return a == 1;
    }
    int dp[maxn]; // min range to make the first x bit good
    ll ans = 0;
    bool valid(int bit){
        dp[0] = 0;
        for(int i=1; i<=n; ++i){
            dp[i] = INF;
            for(int j=i-1; j>=0; --j){
                ll num = pref[i] - pref[j];
                if(((num >> bit) | (ans >> bit)) == (ans >> bit)) dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp[n] <= b;
    }
    void solve(){
        for(int bit=45; bit >= 0; --bit){
            if(!valid(bit)){
                ans |= (1ll << bit);
            }
        }
        cout << ans << '\n';
    }
}
void solve(){
    cin >> n >> a >> b;
    for(int i=1; i<=n; ++i){
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }
    if(case2::check()) case2::solve();
    else case1::solve();
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...