Advertisement
a_chn

Untitled

Dec 5th, 2023
931
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int pref[100001], pref2[100001];
  8. vector<int> c(100000);
  9. vector<pair<int, int> > shops(100000);
  10. vector<int> farms(100000);
  11.  
  12. bool comp(pair<int, int> p, pair<int, int> q) {
  13.     return p.second > q.second;
  14. }
  15.  
  16. int rent(int i) {
  17.     return pref[i];
  18. }
  19.  
  20. void setIO(string s) {
  21.     ios_base::sync_with_stdio(0);
  22.     cin.tie(0);
  23.     freopen((s + ".in").c_str(), "r", stdin);
  24.     freopen((s + ".out").c_str(), "w", stdout);
  25. }
  26.  
  27. int produce(int cow) {
  28.     vector<pair<int, int> > shops2(100000);
  29.     for(int i = 0; i < 100000; ++i) {
  30.         shops2[i] = shops[i];
  31.     }
  32.     int prefsum = pref2[cow];
  33.     int mon = 0;
  34.     int shop_ind = 0;
  35.     //for (int cow = 0; cow < 100000; cow++) {
  36.     while (shops2[shop_ind].first > 0) {
  37.         int sell = min(prefsum, shops2[shop_ind].first);
  38.         prefsum -= sell;
  39.         shops2[shop_ind].first -= sell;
  40.         mon += sell * shops2[shop_ind].second;
  41.         if (shops2[shop_ind].first == 0) {
  42.             shop_ind++;
  43.         }
  44.         if (prefsum == 0) {
  45.             break;
  46.         }
  47.     }
  48.     //}
  49.     return mon;
  50. }
  51. int main() {
  52.     setIO("rental");
  53.     int N, M, R;
  54.     cin >> N >> M >> R; //cows, stores, neighbors
  55.     for (int i = 0; i < N; i++) {
  56.         cin >> c[i];
  57.     }
  58.     sort(c.rbegin(), c.rend());
  59.     for(int i = 1; i <= N; ++i) {
  60.         pref2[i] = pref2[i - 1] + c[i - 1];
  61.     }
  62.     for (int i = 0; i < M; i++) {
  63.         cin >> shops[i].first >> shops[i].second;
  64.     }
  65.     sort(shops.begin(), shops.end(), comp);
  66.     for (int i = 0; i < R; i++) {
  67.         cin >> farms[i];
  68.     }
  69.     sort(farms.rbegin(), farms.rend());  
  70.     for(int i = 1; i <= R; ++i) {
  71.         pref[i] = pref[i - 1] + farms[i - 1];
  72.     }
  73.     int ans = 0;
  74.     for (int i = 0; i <= min(N, R); i++) {
  75.         ans = max(produce(N - i) + rent(i), ans);
  76.     }
  77.     cout << ans << endl;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement