Submission #146481

#	Time	Username	Problem	Language	Result	Execution time	Memory
146481		LittleFlowers__	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1079 ms	1016 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;

#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})
#define instring ({string s;char c=getchar();while(c==' '||c=='\n') c=getchar();while(c!=' '&&c!='\n') s+=c,c=getchar();s;})

#define ll long long
#define FOR(i,a,b) for(auto i=a;i<=b;i++)
#define ROF(i,a,b) for(auto i=b;a<=i;i--)
#define rr(x) " "<<#x<<'='<<x<<" "

#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define pow2(x) (1ll<<x)

#define mt make_tuple
#define pi pair<int,int>
#define x first
#define y second

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define allv(a) a.begin(),a.end()
#define endv(a) (int)a.size()-1

#define ifnot(x) if(!(x))
#define middle(a,b) (a+(b-(a))/2)
#define bp(x) ((x)*(x))
#define bitnum(x) __builtin_popcountll(x)
////////////////////////////////////////// NIRO
#define int ll
const int N=2005;
int n,A,B;
ll a[N];
bitset<2005> f[N];
int s[N];

ll all;
ll SUM(int u,int v){ll res=s[v]-s[u-1];return (res&all)==0;}
main()
{
    //freopen("nr.inp","r",stdin);
    n=in,A=in,B=in;
    FOR(i,1,n) a[i]=in;
    FOR(i,1,n) s[i]=s[i-1]+a[i];
    ROF(bit,1,60)
    {
        memset(f,0,sizeof(f));
        all=on(all,bit);
        FOR(i,1,n) f[i][1]=SUM(1,i);
        /*
        FOR(i,1,n) FOR(j,2,B){
            FOR(k,1,i-1) if(f[k][j-1]&&SUM(k+1,i)) f[i][j]=1;
        }
        */
        FOR(i,1,n){
            FOR(k,1,i-1){
                if(SUM(k+1,i)){
                    //f[k][j-1] -> f[i][j]
                    f[i]|=f[k]<<1;
                }
            }
        }

        all=off(all,bit);
        FOR(i,A,B) if(f[n][i]) all=on(all,bit);

    }
    FOR(i,1,60) {if(bit(all,i)) all=off(all,i);else all=on(all,i);}
    cout<<all;
}

Compilation message (stderr)

sculpture.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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