제출 #107698

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

sculpture

#include <bits/stdc++.h>

using namespace std;

long long target = 0ll; ///1's at that bit means that we want to keep that bit with a value of 0

int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    long long arr[n];
    for(int i = 0;i < n;i++){
        cin >> arr[i];
    }
    long long all = (1ll << 51) - 1;
    for(int i = 1;i < n;i++){
        arr[i] += arr[i-1];
    }
    if(n <= 200){
        bool dp[n][b];
        for(long long bit = 50;bit >= 0;bit--){
            ///check if we can keep that value at 0
            target ^= (1ll << bit);
            for(int i = 0;i < n;i++){
                for(int k = 0;k < b;k++){
                    dp[i][k] = false;
                }
            }
            for(int i = 0;i < n;i++){ ///end
                for(int k = 0;k < b;k++){ ///no. of groups;
                    if(k == 0){
                        if((arr[i] & target) == 0){
                            dp[i][k] = true;
                        }
                        continue;
                    }
                    for(int j = 0;j < i;j++){ ///choosing where to break of the previous group
                        long long presum = arr[i];
                        presum -= arr[j];
                        if(((presum & target) == 0) && dp[j][k-1]){

                            dp[i][k] = true;
                            break;
                        }
                    }
                }
            }

            bool can = false;
            for(int k = a-1;k < b;k++){
                if(dp[n-1][k]){
                    can = true;
                    break;
                }
            }
            if(!can){
                target ^= (1ll << bit);
                //cout << target << "\n";
            }

        }

        cout << (target ^ all) << "\n";
    }
    else{
        int dp[n];

        for(long long bit = 50;bit >= 0;bit--){
            ///check if we can keep that value at 0
            target ^= (1ll << bit);
            for(int i = 0;i < n;i++){
                dp[i] = 102345;
            }
            for(int i = 0;i < n;i++){
                if((arr[i] & target) == 0){
                    dp[i] = 1;
                }
                for(int j = 0;j < i;j++){
                    long long presum = arr[i];
                    presum -= arr[j];
                    if((presum & target) == 0){
                        dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
            if(dp[n-1] > b){
                target ^= (1ll << bit);
            }
        }

        cout << (target ^ all) << "\n";


    }




    return 0;
}

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