제출 #958822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958822		Yahia_Emara	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	348 ms	1136 KiB

sculpture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define LOOP(n) for(int rp=0;rp<(n);rp++)
#define sz(x) int(x.size())
#define dbg(x) cout << (#x) << " : " << x << endl
#define sq(x) ((x)*(x))
#define lsb(x) ((x)&(-(x)))
#define sqm(x) mul((x),(x))
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
#define fsh cout.flush()
#pragma GCC optimize("unroll-loops")
//#define R real()
//#define I imag()
using namespace __gnu_pbds;
using namespace std;
#define OS tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define ofk order_of_key
mt19937_64 rng(time(0));
int rnd(int l,int r){
    return uniform_int_distribution<int>(l,r)(rng);
}
typedef long long ll;
typedef long double dl;
typedef complex<dl>cd;
cd readcd(){
    dl x,y;
    cin >> x >> y;
    return cd(x,y);
}
int MOD=1e9+7;
const int SZ=7e5+7,MSZ=1e7+7;
const ll INF=1e18+7;
const dl eps=1e-18;
ll trig(ll n){
    return n*(n+1)/2;
}
int add(int x,int y,int MOD=MOD){
    x+=y;if(x>=MOD)x-=MOD;
    return x;
}
int sub(int x,int y,int MOD=MOD){
    x-=y;if(x<0)x+=MOD;
    return x;
}
int mul(int x,int y,int MOD=MOD){
    return(x*1ll*y)%MOD;
}
int pwr(int x,ll b,int MOD=MOD){
    int rt=1;
    while(b>0){
        if(b&1)rt=mul(rt,x,MOD);
        x=mul(x,x,MOD),b>>=1;
    }
    return rt;
}
int inv(int x,int MOD=MOD){
    return pwr(x,MOD-2,MOD);
}
int GEO(int S,int r,ll n,int MOD=MOD){
    if(r==1)return mul((n+1)%MOD,S);
    return mul(S,mul(sub(pwr(r,n+1),1),inv(sub(r,1))));
}
ll fp(ll x,ll b){
    ll rt=1;
    while(b>0){
        if(b&1)rt*=x;
        x*=x,b>>=1;
    }
    return rt;
}
struct chash{
    static uint64_t splitmix64(uint64_t x){
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator()(uint64_t x)const{
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
vector<int>rpr(int n){
    vector<int>v;
    while(n>0)v.pb(n%10),n/=10;
    return v;
}
void reform(vector<int>&a){
    for(int i=0;i<sz(a);i++){
        if(a[i]<10)continue;
        if(i==sz(a)-1)a.pb(0);
        a[i+1]+=a[i]/10,a[i]%=10;
    }
    while(sz(a)>1&&a.back()==0)a.pop_back();
}
void neg(vector<int>&a){
    for(int i=0;i<sz(a);i++)a[i]*=-1;
}
vector<int>fftadd(vector<int>a,vector<int>b){
    if(sz(a)<sz(b))swap(a,b);
    for(int i=0;i<sz(b);i++)a[i]+=b[i];
    reform(a);
    return a;
}
vector<int>fftmul(vector<int>a,vector<int>b){
    vector<int>c(sz(a)+sz(b)-1,0);
    for(int i=0;i<sz(a);i++){
        for(int j=0;j<sz(b);j++){
            c[i+j]+=a[i]*b[j];
        }
    }
    reform(c);
    return c;
}
vector<int>fftpwr(vector<int>a,int b){
    vector<int>ans=rpr(1);
    while(b>0){
        if(b&1)ans=fftmul(ans,a);
        a=fftmul(a,a),b>>=1;
    }
    return ans;
}
int getN(){
    int n;cin >> n;
    return n;
}
bitset<2007>dp[2007];
int n,A,B;
ll a[2007];
bool f(ll X){
    dp[n]>>=2007,dp[n][0]=1;
    for(int l=n-1;l>=0;l--){
        ll s=0;
        dp[l]>>=2007;
        for(int r=l;r<n;r++){
            s+=a[r];
            if((s|X)==X)dp[l]|=dp[r+1]<<1;
        }
    }
    for(int i=A;i<=B;i++){
        if(dp[0][i])return 1;
    }
    return 0;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("optmilk.in","r",stdin);
    //freopen("optmilk.out","w",stdout);
    //cout << fixed << setprecision(12);
    int tt=1;
    //cin >> tt;
    LOOP(tt){
        cin >> n >> A >> B;
        for(int i=0;i<n;i++)cin >> a[i];
        ll ans=(1ll<<41)-1;
        for(int i=40;i>=0;i--){
            ans^=1ll<<i;
            if(!f(ans))ans^=1ll<<i;
        }
        cout << ans;
    }
    return 0;
}

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