|
|
вернуться в форумWhy WA1 This is my code, it works good on the sample test, but I get WA1 #include <stdio.h> unsigned int w[20], s, i, n, max, h, j, k, r[20], l[20]; bool a[50001]={1}, u[50001][20]; int main (void){ scanf("%u", &n); for(i = 0; i < n; i++){ scanf("%u", &w[i]); h += w[i]; } for(i = 1; i <= h/2; i++) for(j = 0; j < n; j++){ if(u[i - w[j]][j] == 0 && a[i - w[j]] && i - w[j] >= 0){ a[i]++; for(k = 0; k < n; k++) u[i][k] = u[i-w[j]][k]; u[i][j]++; max = i; j = n; } } printf("%i", h - 2*max); return 0; } Re: Why WA1 It's not clear what your algorithm is (all the single letter variables make for unreadable code), but to quote from another thread about this question, "all polynomial time algorithms are wrong." You must consider all possible combinations, because otherwise there will be an input somewhere that will cause your solution to fail. |
|
|