LashaBukhnikashvili's blog

By LashaBukhnikashvili, 7 years ago, In English

during the contest i tried to check is there or not: such m numbers in array that sum of this numbers will be x.

i wrote code,but i dont know why it is not correct,so need your help:

 int d[10001][101]={0};
 d[0][0]=1;
 for (i=1;i<=n;i++){
     cin>>x;
     for (j=10000;j>=0;j--)
          for (k=0;k<n;k++) 
              if (d[j][k]) 
                  d[j+x][k+1]=1;
 };

d[i][j]=1 if we can find in array j numbers where sum of this numbers will be i,otherwise d[i][j]=0;

P.S using this,i get WA6

UPDATE: i didn't know problem good. but this idea is correct,more formally problems same as above can solve in O(s*n*n) where s is the sum of numbers(all numbers positive).

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Does your solution work for


3 1
15 16 17
14 22 17