### LashaBukhnikashvili's blog

By LashaBukhnikashvili, 7 years ago,

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).

• -9

 » 7 years ago, # | ← Rev. 2 →   +3 Does your solution work for 3 1 15 16 17 14 22 17
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 got it