Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: bradyawn
- PROG: contest
- LANG: C++11
- */
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <deque>
- #include <string>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <utility>
- #include <set>
- #include <unordered_set>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <random>
- #include <cstring>
- #include <functional>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> i2;
- typedef pair<ll,ll> ll2;
- int dp[250001]; //maximize talent
- int w[251];
- int t[251];
- int n, wReq;
- int main()
- {
- ifstream inf("talent.in");
- ofstream outf("talent.out");
- //outf << setprecision(10);
- ios_base::sync_with_stdio(0); inf.tie(0);
- inf >> n >> wReq;
- int mxTalent = 0;
- for (int i = 1; i <= n; i++)
- {
- inf >> w[i] >> t[i];
- mxTalent += t[i];
- }
- for (int i = 1; i <= 250000; i++) dp[i] = 1e9;
- for (int i = 1; i <= n; i++) //considering item i
- {
- for (int j = mxTalent; j >= 0; j--) //knapsack talent j
- if (j - t[i] >= 0) dp[j] = min(dp[j], dp[j-t[i]] + w[i]);
- }
- int ans = 0;
- for (int i = 1; i <= mxTalent; i++)
- if (dp[i] >= wReq) ans = max(ans, int(1000.0*i/dp[i]));
- outf << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement