Submission #7586

#	Time	Username	Problem	Language	Result	Execution time	Memory
7586		dohyun0324	경비원 (GA8_guard)	C++98	21 / 100	380 ms	1096 KiB

guard

#include<stdio.h>
int cnt,n,a[2510],m,ch[30],w;
int gcd(int x,int y)
{
    if(x%y==0) return y;
    return gcd(y,x%y);
}
void dfs(int x)
{
    int i;
    if(x==n)
    {
        if(w>=2)
        {
            cnt++;
        }
        return;
    }
    dfs(x+1);
    for(i=1;i<=w;i++)
    {
        if(gcd(ch[i],a[x+1])!=1) break;
    }
    if(i!=w+1) return;
    ch[++w]=a[x+1];
    dfs(x+1);
    ch[w--]=0;
}
int main()
{
    int i,j,s;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(m<a[i]) m=a[i];
    }
    //subtask 1,2
    if(n<=44)
    {
        dfs(1);
        ch[++w]=a[1];
        dfs(1);
        printf("%d",cnt);
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 27
• Subtask 5: 0 / 36