Submission #752819

#	Time	Username	Problem	Language	Result	Execution time	Memory
752819		winter0101	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	93 ms	380 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
int n,x,y;
long long a[2009];
long long b[2009];
int dp[2009];
bool f[109][109];
bool check(long long mask){
if (n<=100){
    for1(i,1,n+1){
    for1(j,0,y){
    f[i][j]=0;
    }
    }
    f[1][0]=1;
    for1(i,1,n){
    for1(j,i,n){
    long long value=((b[j]-b[i-1]));
    if ((value&mask)!=value)continue;
    for1(j1,0,y-1){
    if (!f[i][j1])continue;
    f[j+1][j1+1]=max(f[j+1][j1+1],f[i][j1]);
    }
    }
    }
    for1(i,x,y){
    if (f[n+1][i])return 1;
    }
    return 0;
}
else {
    for1(i,2,n+1){
    dp[i]=3009;
    }
    for1(i,1,n){
    for1(j,i,n){
    long long value=((b[j]-b[i-1]));
    if ((value&mask)==value){
        dp[j+1]=min(dp[j+1],dp[i]+1);
    }
    }
    }
    return (dp[n+1]<=y);
}
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>x>>y;
    for1(i,1,n)cin>>a[i];
    for1(i,1,n){
    b[i]=b[i-1]+a[i];
    }
    long long ans=(1ll<<41)-1;
    for2(i,40,0){
    if (check(ans-(1ll<<i))){
        ans-=(1ll<<i);
    }
    }
    cout<<ans;
}

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