Submission #14814

#	Time	Username	Problem	Language	Result	Execution time	Memory
14814		eaststar	Sequence (BOI14_sequence)	C++98	100 / 100	121 ms	8116 KiB

sequence

#include <stdio.h>
#include <algorithm>
#define ffs(a) __builtin_ffs(a)
using namespace std;
typedef long long LL;
int a[18][100010];
LL dfs(int p,int A[],int an,int w){
    int i,j,k,v,z;
    LL mn=102345678900000L;
    if(an==1){
        if(A[0]<=1)return A[0]*10;
        v=A[0]&1022;
        mn=(ffs(v)-1)*(A[0]&1? 10:1);
        for(v-=v&-v;v;v-=v&-v)mn=mn*10+ffs(v)-1;
        return mn;
    }
    for(i=0;i<=9-w;++i){
        k=i,v=z=0;
        int *B=a[p+1],bn=0;
        for(j=0;j<an;++j){
            v|=A[j]^(A[j]&(1<<k));
            if(A[j]&1&&!k)z=1;
            k=(k+1)%10;
            if(!k||j+1==an){
                B[bn++]=v;
                v=0;
            }
        }
        LL rv=dfs(p+1,B,bn,i==9&&an<=2)*10+i;
        if(!rv&&z)rv=10;
        mn=min(mn,rv);
    }

    return mn;
}
int main(){
    int i,k,an=0,v;
    scanf("%d",&k);
    for(i=1;i<=k;++i){
        scanf("%d",&v);
        a[0][an++]=1<<v;
    }
    printf("%lld",dfs(0,a[0],an,0));
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33