Submission #582473

#	Time	Username	Problem	Language	Result	Execution time	Memory
582473		gg123_pe	Bali Sculptures (APIO15_sculpture)	C++14	25 / 100	38 ms	896 KiB

sculpture

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,int> ii; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 2005; 
const ll inf = 1e18 + 10;


int n, a, b, x[55];
bool dp[55][21][505]; 

bool on(int x, int pos){
    return (x&(1LL<<pos)); 
}
int main(){
    cin >> n >> a >> b; 

    f(i,1,n+1) cin >> x[i]; 

    if(n <= 20){    
        ll ans = inf; 

        f(i,1,(1<<n)){
            int xi = __builtin_popcount(i); 
            if(xi < a or b < xi or i%2 == 0) continue; 

            ll res = 0, id = 0; 

            while(id < n){
                ll c = x[id+1]; 
                id++; 
                
                while(id < n and !on(i,id)) {
                    c += x[id+1]; 
                    id++; 
                }
                res |= c; 
                
            }
        
            ans = min(ans, res); 
        }
        cout << ans << "\n"; 
        return 0;
    }
    dp[0][0][0] = 1; 

    f(i,1,n+1){ 
        int s = 0; 
        fa(j,i,1){
            s += x[j]; 

            fa(g,min(20,i),1){
                f(k,0,501) {
                    if(dp[j-1][g-1][k])
                        dp[i][g][(k|s)] = 1; 
                }
            }
    
        }
    }
    int ans = 10000; 

    f(i,a,b+1){
        f(j,0,505) if(dp[n][i][j]) ans = min(ans, j); 
    }
    cout << ans << "\n"; 
    return 0; 
}

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