Advertisement
YanikusGG

problem D

Jun 22nd, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <string>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10.  
  11. //#include "BigInt.h"
  12.  
  13. using namespace std;
  14.  
  15. #define ll long long
  16. #define ull unsigned long long
  17. const ll INF = 999999999999999999;
  18. const double PI = acos(-1.0);
  19.  
  20. void stop()
  21. {
  22. #ifndef ONLINE_JUDGE
  23.     system("pause");
  24. #endif
  25.     exit(0);
  26. }
  27.  
  28. ll A[305];
  29. pair<ll,ll> F[305];
  30.  
  31. int main()
  32. {
  33.     freopen("d.in", "r", stdin);
  34.     freopen("d.out", "w", stdout);
  35.     ios::sync_with_stdio(false);
  36.  
  37.     ll m, d, n;
  38.     cin >> m >> d >> n;
  39.     for (ll i = 0; i < n; i++)
  40.     {
  41.         cin >> A[i];
  42.     }
  43.     F[0].first = 1;
  44.     F[0].second = 0;
  45.     for (ll i = 0; i < n; i++)
  46.     {
  47.         for (ll j = n; j >= 0; j--)
  48.         {
  49.             if (F[j].first != 0 && F[j].second + A[i] <= d && (F[j+1].first==0 || F[j+1].first>F[j].first || (F[j+1].first==F[j].first && F[j+1].second>F[j].second+A[i])))
  50.             {
  51.                 F[j + 1].first = F[j].first;
  52.                 F[j + 1].second = F[j].second + A[i];
  53.             }
  54.             else if (F[j].first != 0 && F[j].first < m && (F[j + 1].first == 0 || F[j + 1].first>F[j].first+1 || (F[j + 1].first == F[j].first+1 && F[j + 1].second>A[i])))
  55.             {
  56.                 F[j + 1].first = F[j].first+1;
  57.                 F[j + 1].second = A[i];
  58.             }
  59.         }
  60.     }
  61.     for (ll i = n; i >= 0; i--)
  62.     {
  63.         if (F[i].first != 0)
  64.         {
  65.             cout << i;
  66.             stop();
  67.         }
  68.     }
  69.  
  70.     stop();
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement