Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define thicc(boi) boi.size()
- #define magiczne ios_base::sync_with_stdio(0);
- #define linijki cin.tie(NULL);
- using namespace std;
- struct basket{
- double h, w, v;
- };
- basket xd[10007];
- bool cmp(basket i, basket j)
- {
- return i.h > j.h;
- }
- int main()
- {
- magiczne linijki;
- int n, g, sum = 0, res = 0;
- cin >> n >> g;
- for (int i = 0;i<n;i++)
- {
- cin >> xd[i].w >> xd[i].v;
- if (xd[i].w == 0)
- xd[i].h = LDBL_MAX;
- else xd[i].h = xd[i].v/xd[i].w;
- sum += xd[i].w;
- }
- if (sum < g)
- {
- cout << "NIE\n";
- return 0;
- }
- sum -= g; //pozbycie się maksymalnie dużo tych pozostałych losów, by usunąć możliwie mało wygrywających
- sort(xd, xd + n, cmp); //sortowanie po stosunku
- for (int i = 0;i<n;i++)
- {
- if (xd[i].w <= sum) //ciągły problem plecakowy tak działa chyba
- {
- sum -= xd[i].w;
- xd[i].w = 0;
- xd[i].v = 0;
- }
- else
- {
- xd[i].w -= sum;
- break;
- }
- }
- for (int i = 0;i<n;i++)
- res += xd[i].v + xd[i].w; //zliczamy to, co zostało
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement