제출 #1288124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288124		lambd47	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	98 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;
const int MOD=1e9+7;

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
        //ops faz um pseudo aliens trick ent
        resp^=((int)1<<i);
        vector<int> dp(n,MOD);
        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]=min(dp[i],dp[j]+1);
            }
        }
        bool ok=0;
        if(dp[n-1]>rig)resp+=((int)1<<i);
    }
    cout<<resp;
    }
   
}

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

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