제출 #1288122

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

sculpture

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())

//f trie fica muito longo

const int lg=45;


void solve(){
    int n,lef,rig;cin>>n>>lef>>rig;
    
    int resp=((int)1<<(lg))-1;
    vector<int> vec(n);
    L(i,0,n-1)cin>>vec[i];

    vector<int> pref=vec;
    L(i,1,n-1)pref[i]+=pref[i-1];
    if(lef!=1){
    R(i,lg-1,0){
        //tento fazer a resposta sem esse bit
        resp^=((int)1<<i);
        vector<vector<bool>> dp(n,vector<bool>(rig+1,0));
        L(i,0,n-1){
            L(k,1,rig){
                if(k==1){
                    if((pref[i]&resp)==pref[i])dp[i][1]=1;
                    continue;
                }
                L(j,0,i-1){//bruto o vizinho
                    if(dp[j][k-1]&&(((pref[i]-pref[j])&(resp))==pref[i]-pref[j]))dp[i][k]=1;
                }
            }
        }
        bool ok=0;
        L(i,lef,rig)if(dp[n-1][i])ok=1;
        if(!ok)resp+=((int)1<<i);
    }
    cout<<resp;
    }
    else{
        R(i,lg-1,0){
        //tento fazer a resposta sem esse bit
        resp^=((int)1<<i);
        vector<bool> dp(n,0);
        L(i,0,n-1){
            if(((pref[i]&resp)==pref[i]))dp[i]=1;
            L(j,0,i-1){
                if(dp[j]&&(((pref[i]-pref[j])&(resp))==pref[i]-pref[j]))dp[i]=1;
            }
        }
        if(!dp[n-1])resp+=((int)1<<i);
    }
    cout<<resp;
    }
   
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}

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