Submission #107106

#	Time	Username	Problem	Language	Result	Execution time	Memory
107106		tduong0806	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	118 ms	904 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1ll<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
#define read2(a,b) read(a),read(b)
#define read3(a,b,c) read(a),read(b),read(c)
const int N=2010;
int n,A,B,F[N],a[N];
ll f[N][N],s[N],kq;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("SCULPTURE.inp","r",stdin);
    //freopen("SCULPTURE.out","w",stdout);
    cin>>n>>A>>B;
    forinc(i,1,n) cin>>a[i],s[i]=s[i-1]+a[i];
    if(n<=100)
    {
        ll S=0;
        f[0][0]=1;
        fordec(i,41,1)
        {
            ll tg=onbit(S,i);
            forinc(i,1,n) forinc(j,1,B)
            {
                f[i][j]=0;
                forinc(t,0,i-1) if(!(tg&(s[i]-s[t]))&&f[t][j-1]) f[i][j]=1;
            }
            bool ok=0;
            forinc(i,A,B) if(f[n][i]) ok=1;
            if(ok) S=tg;
            else kq=onbit(kq,i);
        }
        return cout<<kq,0;
    }
    ll S=0;
    F[0]=0;
    fordec(i,41,1)
    {
        ll tg=onbit(S,i);
        forinc(i,1,n)
        {
            F[i]=1e4;
            forinc(j,0,i-1) if(!(tg&(s[i]-s[j]))) F[i]=min(F[i],F[j]+1);
        }
        if(F[n]<=B) S=tg;
        else kq=onbit(kq,i);
    }
    return cout<<kq,0;
}

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