제출 #238967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238967		aggu_01000101	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	128 ms	512 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
int n, a, b;
int arr[2005];
int pow2[45];
bool check(int ans, int lat, int curr){
    //find overlap of first (lat - 1) powers
    int temp = ans|curr;
    int diff = temp - ans;
    //sum of first (lat - 1) powers = 2^lat - 1
    if(diff > (pow2[lat] - 1)) return false;
    return true;
}
bool dp(int ans, int lat){ //o(n^2)
    int dp[n+1]; //minimum number of partitions required
    dp[0] = 0;
    for(int i = 1;i<=n;i++){
        dp[i] = INF;
        int sum = 0;
        for(int j = i;j>=1;j--){
            sum+=arr[j];
            if(check(ans, lat, sum)) dp[i] = min(dp[i], dp[j-1] + 1);
        }
        //cout<<"dp["<<i<<"] = "<<dp[i]<<" for ans = "<<ans<<" and lat = "<<lat<<"\n";
    }
    if(dp[n]<=b) return true;
    return false;
}
int dp1(int ans, int lat){//o(n^3)
    bool dp[n+1][n+1]; //whether it's possible
    for(int i = 0;i<=n;i++) dp[0][i] = false;
    dp[0][0] = true;
    for(int i = 1;i<=n;i++){
        for(int k = 0;k<=n;k++){
            dp[i][k] = false;
        }
        int sum = 0;
        for(int j = i;j>=1;j--){
            sum+=arr[j];
            if(check(ans, lat, sum)){
                for(int k = 1;k<=n;k++){
                    if(dp[j-1][k-1]) dp[i][k] = true;
                }
            }
        }
    }
    bool found = false;
    for(int i = a;i<=b;i++) found = found || dp[n][i];
    return found;
}
bool f(int ans, int lat){ //o(n^3)
    if(a==1){
        return dp(ans, lat);
    }
    else{
        return dp1(ans, lat);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>a>>b;
    for(int i = 1;i<=n;i++) cin>>arr[i];
    pow2[0] = 1;
    for(int i = 1;i<45;i++) pow2[i] = pow2[i-1]*2;
    int ans = 0;
    for(int i = 40;i>=0;i--){
        bool can = f(ans, i);
        //cout<<i<<" "<<can<<"\n";
        if(!can) ans+=pow2[i];
    }
    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