Advertisement
Manh_LK

Cây khế (TLE)

Mar 31st, 2020
1,049
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. using namespace std;
  4. int n, k, sum, res;
  5. int C[55];
  6. int A[300];
  7. void quickSort(int l, int r)
  8. {
  9.     int pivot = C[(l + r) / 2];
  10.     int i = l;
  11.     int j = r;
  12.     while (i <= j)
  13.     {
  14.         while (C[i] < pivot) i++;
  15.         while (C[j] > pivot) j--;
  16.         if (i <= j)
  17.         {
  18.             int tmpt = C[i];
  19.             C[i] = C[j];
  20.             C[j] = tmpt;
  21.             i++; j--;
  22.         }
  23.     }
  24.     if (l < j) quickSort(l, j);
  25.     if (r > i) quickSort(i, r);
  26. }
  27. void Try(int i)
  28. {
  29.     for (int j = 0; j < k; j++)
  30.     {
  31.         A[i] = C[j];
  32.         if (A[i] >= A[i - 1] && (sum + A[i] <= n))
  33.         {
  34.             sum += A[i];
  35.             if (sum == n) res += 1;
  36.             else Try(i + 1);
  37.             sum -= A[i];
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     freopen("input.txt", "r", stdin);
  44.     cin >> n >> k;
  45.     for (int i = 0; i < k; i++)
  46.     {
  47.         cin >> C[i];
  48.     }
  49.     quickSort(0, k - 1);
  50.     sum = 0; A[0] = 0; res = 0;
  51.     Try(1);
  52.     cout << res;
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement