Advertisement
ProgNeo

Untitled

Jun 21st, 2021 (edited)
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits.h>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> P, W;
  8. int n;
  9. int E, F;
  10. vector<int> MAX, MIN;
  11.  
  12. bool input()
  13. {
  14.     cin >> E >> F;
  15.     if (1 > E || E > 10000 || F < E || 1 > F || F > 10000)
  16.     {
  17.         cout << "This is impossible.";
  18.         return false;
  19.     }
  20.     cin >> n;
  21.     if (1 > n || n > 500)
  22.     {
  23.         cout << "This is impossible.";
  24.         return false;
  25.     }
  26.     MAX = vector<int>(F - E + 1, INT_MIN);
  27.     MIN = vector<int>(F - E + 1, INT_MAX);
  28.     P.resize(n); W.resize(n);
  29.     for (int i = 0; i < n; i++)
  30.     {
  31.         cin >> P[i] >> W[i];
  32.         if (1 > P[i] || P[i] > 50000 || 1 > W[i] || W[i] > 10000 || P[i] * W[i] > F)
  33.         {
  34.             cout << "This is impossible.";
  35.             return false;
  36.         }
  37.     }
  38. }
  39.  
  40. void solve()
  41. {
  42.     MIN[0] = 0;
  43.     MAX[0] = 0;
  44.     for (int i = 0; i < MIN.size(); i++)
  45.     {
  46.         for (int j = 0; j < W.size(); j++)
  47.         {
  48.             if (i - W[j] >= 0 && MIN[i - W[j]] != INT_MAX)
  49.             {
  50.                 MIN[i] = min(MIN[i], MIN[i - W[j]] + P[j]);
  51.                 MAX[i] = max(MAX[i], MAX[i - W[j]] + P[j]);
  52.             }
  53.         }
  54.     }
  55.  
  56. }
  57.  
  58. void output()
  59. {
  60.     if (MIN.back() == INT_MAX)
  61.         cout << "This is impossible.";
  62.     else
  63.         cout << MIN.back() << ' ' << MAX.back();
  64. }
  65.  
  66. int main()
  67. {
  68.     if (input() == false) return 0;
  69.     solve();
  70.     output();
  71.  
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement