제출 #1358956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358956		nathlol2	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	142 ms	45796 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int n, a, b, ans, pf[N], dist[N];
bool dp[N][N], fuck[N];
vector<int> can[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> a >> b;
    for(int i = 1;i<=n;i++){
        cin >> pf[i];
        pf[i] += pf[i - 1];
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<i;j++) can[i].push_back(j);
    }
    for(int bit = 45;bit>=0;bit--){
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        vector<int> ncan[N];
        bool ok = 0;
        if(a != 1){
            for(int k = 1;k<=b;k++){
                for(int i = 1;i<=n;i++){
                    if(k == 1){
                        for(auto x : can[i]){
                            int cc = pf[i] - pf[x];
                            bool f = 1;
                            for(int bb = bit;bb<=45;bb++){
                                if((cc & (1LL << bb)) && !fuck[bb]){
                                    f = 0;
                                    break;
                                }
                            }
                            if(f){
                                dp[i][k] |= dp[x][k - 1];
                                ncan[i].push_back(x);
                            }
                        }
                    }else{
                        for(auto x : ncan[i]){
                            dp[i][k] |= dp[x][k - 1];
                        }
                    }
                }
            }
            for(int i = a;i<=b;i++) ok |= dp[n][i];
        }else{
            for(int i = 1;i<=n;i++){
                for(auto x : can[i]){
                    int cc = pf[i] - pf[x];
                    bool f = 1;
                    for(int bb = bit;bb<=45;bb++){
                        if((cc & (1LL << bb)) && !fuck[bb]){
                            f = 0;
                            break;
                        }
                    }
                    if(f){
                        ncan[i].push_back(x);
                    }
                }
            }
            for(int i = 0;i<=n;i++) dist[i] = -1;
            queue<int> q;
            q.push(n);
            dist[n] = 0;
            while(!q.empty()){
                int u = q.front();
                q.pop();
                for(auto v : ncan[u]){
                    if(dist[v] == -1){
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
            if(dist[0] <= b && dist[0] != -1) ok = 1;
        }
        if(ok){
            for(int i = 1;i<=n;i++) can[i] = ncan[i];
        }else{
            fuck[bit] = 1;
            ans += (1LL << bit);
        }
    }
    cout << ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 16 / 16
• 서브태스크 3: 21 / 21
• 서브태스크 4: 25 / 25
• 서브태스크 5: 29 / 29