Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <limits.h>
- using namespace std;
- vector<int> P, W;
- int n;
- int E, F;
- vector<int> MAX, MIN;
- bool input()
- {
- cin >> E >> F;
- if (1 > E || E > 10000 || F < E || 1 > F || F > 10000)
- {
- cout << "This is impossible.";
- return false;
- }
- cin >> n;
- if (1 > n || n > 500)
- {
- cout << "This is impossible.";
- return false;
- }
- MAX = vector<int>(F - E + 1, INT_MIN);
- MIN = vector<int>(F - E + 1, INT_MAX);
- P.resize(n); W.resize(n);
- for (int i = 0; i < n; i++)
- {
- cin >> P[i] >> W[i];
- if (1 > P[i] || P[i] > 50000 || 1 > W[i] || W[i] > 10000 || P[i] * W[i] > F)
- {
- cout << "This is impossible.";
- return false;
- }
- }
- }
- void solve()
- {
- MIN[0] = 0;
- MAX[0] = 0;
- for (int i = 0; i < MIN.size(); i++)
- {
- for (int j = 0; j < W.size(); j++)
- {
- if (i - W[j] >= 0 && MIN[i - W[j]] != INT_MAX)
- {
- MIN[i] = min(MIN[i], MIN[i - W[j]] + P[j]);
- MAX[i] = max(MAX[i], MAX[i - W[j]] + P[j]);
- }
- }
- }
- }
- void output()
- {
- if (MIN.back() == INT_MAX)
- cout << "This is impossible.";
- else
- cout << MIN.back() << ' ' << MAX.back();
- }
- int main()
- {
- if (input() == false) return 0;
- solve();
- output();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement