12455 - Bars

[ioi]

pls help me out.. what's wrong with this one ????
I got WA

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MM 200008

int inp[25],track[MM];

int solve(int sum,int n,int val)
{
    int i,j,k,l,inx;
    track[0]=1;
    for(i=1;i<=sum;i++)
    {
        track[i]=0;
    }
    for(i=0;i<n;i++)
    {
        for(j=sum;j>=0;j--)
        {
            if(track[j]==1)
            {
                inx=j+inp[i];
                if(track[inx]!=1 && inx<=sum)
                {
                    track[inx]=1;
                }
            }
        }
    }
    return track[val];
}

int main()
{
    int test,t,i,j,blen,nbar,sum,res;
    scanf("%d",&test);
    for(t=0;t<test;t++)
    {
        scanf("%d",&blen);
        scanf("%d",&nbar);
        sum=0;
        for(i=0;i<nbar;i++)
        {
            scanf("%d",&inp[i]);
            sum+=inp[i];
        }
        res=solve(sum,nbar,blen);
        if(res)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
        memset(inp,0,sizeof(inp));
    }
    return 0;
}

[brianfry713]

If blen>sum print NO.

[shuvrothpol1]

wa.>>>>

Code: Select all

#include <stdio.h>
int a[20];
void sort_des(int p);
int result (int n,int p,int a[]);

int main ()

{
 int t,n,p,i,j,x;

 scanf ("%d",&t);
 for (j=0;j<t;j++)
  {
	 scanf ("%d%d",&n,&p);

	 for (i=0;i<p;i++)
	  scanf ("%d",&a[i]);
   if (n!=0){
	 sort_des(p);
	 x=result(n,p,a);

	 if (x==1)
	 printf ("NO\n");
	}
  else
   printf ("YES\n");
 }
 return 0;
}

void sort_des(int p)

{
 int i,j,temp;

 for (i=0;i<p-1;i++)
  {
	for (j=0;j<p-i;j++)
	 {
		if (a[j]<a[j+1])
		 {
			temp=a[j];
			a[j]=a[j+1];
			a[j+1]=temp;
		 }
	 }
  }
}


int result (int n,int p,int a[])
{
 int cal=0,i;
 for (i=0;i<p;i++)
  {
	 if (cal+a[i]<=n)
	  {
		cal+=a[i];
		 if (cal==n)
		  {
			 printf ("YES\n");
			 return 0;
		  }
	  }
  }
  return 1;
}

[brianfry713]

Try input:
1
5
3
4 3 2

[prokawsar]

Getting WA Please Help

Code: Select all

/*Date: 25.11.15
Problem: 12455 Bars
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int compare(const void *a, const void *b){
	return ( *(int*) a - *(int*) b);
}

int main()
{
    int t, i, j, l, m;
	int num[22];
	int x, c, n;

	scanf("%d", &t);

	while(t--){

	scanf("%d", &c);
	scanf("%d", &n);
	x=1;

	for(i=0; i<n; i++){
		scanf("%d", &num[i]);
	}
	if(c==0) {
		printf("YES\n");
		continue;
	}
	qsort(num, n, sizeof(int), compare);

	for(i=n-1; i>=0; i--){
		if(num[i]==c){
			printf("YES\n");
				x=0;
			break;
		}
		else if(num[i]> c){
			continue;
		}
		
		for(j=i-1; j>=0; j--){
			if((num[i]+num[j])>c){
				continue;
			}
			else if(num[i]+num[j]==c){
				printf("YES\n");
				x=0;
				break;
			}
			else num[i]+=num[j];
			if(num[i]==c){
				printf("YES\n");
				x=0;
				break;
			}

		}
		if(x==0) break;
	}
	if(x==1) printf("N0\n");
	}


    return 0;
}