제출 #1273369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273369		hgmhc	Bali Sculptures (APIO15_sculpture)	C++20	21 / 100	2 ms	584 KiB

sculpture

#include <bits/stdc++.h>
using namespace std; using ll = long long; using ii = pair<ll,ll>; using vi = vector<ll>;
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
#define per(i,a,b) for (ll i = (b); i >= (a); --i)
#define all(x) (x).begin(), (x).end()
#define siz(x) ll((x).size())
#define Mup(x,y) (x = max(x,y))
#define mup(x,y) (x = min(x,y))
#define fi first
#define se second
#define pb push_back
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define int do not use int

const ll N = 2003;
ll n, a, b, y[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> a >> b;
    
    ll p[N]{};
    rep(i,1,n) cin >> y[i], p[i] = p[i-1] + y[i];
    
    if (a > 1) {
        
        assert(0);
    }
    
    ll lp = 0;
    
    per(k,0,29) {
        
        ll dp[N];
        fill(dp, dp+N, 1e9);
        dp[0] = 0;
        
        rep(i,1,n) {
            rep(j,0,i-1) {
                ll s = p[i]-p[j];
                
                //       [           s[k]]
                // s>>k = s[t] s[t-1] ... s[1] s[0]]
                if (((s|lp)>>k) != (lp>>k)) continue;
                
                dp[i] = min(dp[i], dp[j] + 1);
            }
            // cerr << dp[i] << ' ';
        }
        // cerr << endl;
        
        if (dp[n] > b) {
            lp ^= 1<<k;
            // cerr << 0;
        }
        else {
            // cerr << 1;
        }
    }
    
    cout << lp;
}

/*

N <= 2000

X조각 내서 각 조각의 구간합을 전체에 OR 취한 값을 최소화 시켜야 한다

X <= B에 대해서 해결하면 된다

일단 조각을 잘 내서 전부 2^k 미만으로 바꿀 수 있다면 이 k를 줄이는 것이 우선이다

dp[i]:=1..i까지를 쪼갰을 때, 상위 비트 x로 만드는 최소 조각 수


*/

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