Submission #656311

#	Time	Username	Problem	Language	Result	Execution time	Memory
656311		Ronin13	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1080 ms	31684 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pb push_back
#define epb empalce_back
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;


int main(){
    int n; cin >> n;
    int a; cin >> a;
    int b; cin >> b;
    ll x[n + 1];
    for(int i= 1; i <= n; i++) cin >> x[i];
    ll pref[n + 1];
    pref[0] = 0;
    for(int i = 1; i <= n; i++)
        pref[i] = pref[i - 1] + x[i];
    if(n <= 100){
        ll ans = 0;
        ll cnt[n + 1][n + 1];
        for(int j = 0; j <= n; j++){
            for(int i = j + 1; i <= n; i++){
                cnt[j][i] = 0;
            }
        }
        int C = 0;
        for(int u = 50; u >= 1; u--){
            ll mod = (1LL << u);
            bool dp[n + 1][n + 1];
            for(int i= 0; i <= n; i++){
                for(int j = 0; j <= n; j++){
                    dp[i][j] = false;
                }
            }

            dp[0][0] = true;

            for(int i = 1; i <= n; i++){
                for(int j = i - 1; j >= 0; j--){
                    ll val = pref[i] - pref[j];
                    if((val % mod) >= (mod / 2)) continue;
                    if(cnt[j][i] == C){
                        for(int x = 0; x < n; x++){
                            dp[i][x + 1] |= dp[j][x];
                        }
                    }
                }
            }
            //cout << dp[n][1] << "\n";
            bool ind = false;
            for(int i = a; i <= b; i++){
                if(dp[n][i]) ind = true;
            }
            if(ind){
                C++;
                for(int i= 1; i <= n; i++){
                    for(int j = i - 1; j >= 0; j--){
                        ll val = pref[i] - pref[j];
                        if((val % mod) < (mod / 2)) cnt[j][i]++;
                    }
                }
            }
            else ans += (1LL << (u - 1));
        }
        cout << ans;
        return 0;
    }
    ll ans = 0;
        ll cnt[n + 1][n + 1];
        for(int j = 0; j <= n; j++){
            for(int i = j + 1; i <= n; i++){
                cnt[j][i] = 0;
            }
        }
        int C = 0;
        for(int u = 50; u >= 1; u--){
            ll mod = (1LL << u);
            int dp[n + 1];
            for(int i= 0; i <= n; i++){
                dp[i] = 1e9 + 1;
            }

            dp[0] = 0;

            for(int i = 1; i <= n; i++){
                for(int j = i - 1; j >= 0; j--){
                    ll val = pref[i] - pref[j];
                    if((val % mod) >= (mod / 2)) continue;
                    if(cnt[j][i] == C){
                       dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
            //cout << dp[n][1] << "\n";
            bool ind = false;
            if(dp[n] <= b) ind = true;
            if(ind){
                C++;
                for(int i= 1; i <= n; i++){
                    for(int j = i - 1; j >= 0; j--){
                        ll val = pref[i] - pref[j];
                        if((val % mod) < (mod / 2)) cnt[j][i]++;
                    }
                }
            }
            else ans += (1LL << (u - 1));
        }
        cout << ans;
    return 0;
}

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