Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- bool isDiag = false;
- struct Store{
- int q, p;
- Store(){};
- Store(int q, int p):q(q), p(p){};
- };
- int cows[100001];
- Store stores[100001];
- int rents[100001];
- int main(){
- //isDiag = true;
- freopen( "rental.in", "r", stdin);
- long long ans = 0;
- int N, M, R ;
- cin >> N >> M >> R;
- for (int i = 1; i <= N; i++) cin >> cows[i];
- for (int i = 1; i <= M; i++) cin >> stores[i].q >> stores[i].p;
- for (int i = 1; i <= R; i++) cin >> rents[i];
- sort(cows+1, cows+1+N, greater<int>());
- sort(stores+1, stores+1+M, [&](Store a, Store b){
- return a.p > b.p;
- });
- sort(rents+1, rents+1+R, greater<int>());
- if (isDiag)
- {
- for (int i = 1; i <= N; i++) cout << "cows: " << cows[i] << endl;
- for (int i = 1; i <= M; i++) cout << "stores p: " << stores[i].p << ", q: " << stores[i].q<< endl;
- for (int i = 1; i <= R; i++) cout << "rents: " << rents[i]<< endl;
- }
- int ci = 1, si = 1, ri = 1;
- while (ci <= N)
- {
- int money = 0;
- int milk = cows[ci];
- int tsi = si;
- int r_milk;
- while (tsi <= M)
- {
- int a_milk = min(stores[tsi].q, milk);
- money += a_milk * stores[tsi].p;
- milk -= a_milk;
- if (milk == 0)
- {
- r_milk = a_milk;
- break;
- }else
- {
- tsi++;
- }
- }
- if (ri > R || money > rents[ri])
- {
- // sell to store
- ans += money;
- si = tsi;
- if(si <= M) stores[si].q -= r_milk;
- ci++;
- }else
- {
- ans += rents[ri++];
- N--; // release less productive cow to rent
- }
- }
- if(!isDiag) freopen("rental.out", "w", stdout);
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
