v 0. Pasted by UnderFelixAbove as cpp at 2010-05-18 21:52:21 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 3.
  2. // 3C. Копилка [piggy]
  3. // ibelyaev: 02Mar2010
  4. #include <iostream>
  5. #include <vector>
  6. #include <limits.h>
  7.  
  8. using namespace std;
  9.  
  10. vector<int> P,W;
  11. int n;
  12. int E,F;
  13. vector<int> MAX, MIN;
  14. void input()
  15. {
  16.     cin>>E>>F;
  17.     cin>>n;
  18.     MAX = vector<int>(F - E + 1,INT_MIN);
  19.     MIN = vector<int>(F - E + 1,INT_MAX);
  20.     P.resize(n); W.resize(n);
  21.     for (int i=0;i<n;i++)
  22.         cin>>P[i]>>W[i];
  23. }
  24. void solve()
  25. {
  26.     MIN[0] = 0;
  27.     MAX[0] = 0;
  28.     for (int i = 0;i<MIN.size();i++)
  29.     {
  30.         for (int j=0;j<W.size();j++)
  31.         {
  32.             if (i - W[j]>=0 && MIN[i-W[j]]!=INT_MAX)
  33.             {
  34.                 MIN[i] = min(MIN[i],MIN[i-W[j]] + P[j]);
  35.                 MAX[i] = max(MAX[i],MAX[i-W[j]] + P[j]);
  36.             }
  37.         }
  38.     }
  39.    
  40. }
  41. void output()
  42. {
  43.     if (MIN.back()==INT_MAX)
  44.         cout<<"This is impossible.";
  45.     else
  46.         cout<<MIN.back()<<' '<<MAX.back();
  47. }
  48. int main()
  49. {
  50.     input();
  51.     solve();
  52.     output();
  53.  
  54.     return 0;
  55. }


Editing is locked.