Advertisement
a_chn

Untitled

Dec 5th, 2023
862
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8.  
  9. int pref[100001], pref2[100001];
  10. vector<int> c(100000);
  11. vector<pair<int, int> > shops(100000);
  12. vector<int> farms(100000);
  13. int shop_ind;
  14. int mon;
  15.  
  16.  
  17. bool comp(pair<int, int> p, pair<int, int> q) {
  18.     return p.second > q.second;
  19. }
  20.  
  21. int rent(int i) {
  22.     return pref[i];
  23. }
  24.  
  25. void setIO(string s) {
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0);
  28.     freopen((s + ".in").c_str(), "r", stdin);
  29.     freopen((s + ".out").c_str(), "w", stdout);
  30. }
  31.  
  32. int produce(int cow) {
  33.     if(cow == 0) return 0;
  34.     int prefsum = c[cow - 1];
  35.     //for (int cow = 0; cow < 100000; cow++) {
  36.     while (shops[shop_ind].first > 0) {
  37.         int sell = min(prefsum, shops[shop_ind].first);
  38.         prefsum -= sell;
  39.         shops[shop_ind].first -= sell;
  40.         mon += sell * shops[shop_ind].second;
  41.         if (shops[shop_ind].first == 0) {
  42.             shop_ind++;
  43.         }
  44.         if (prefsum == 0) {
  45.             break;
  46.         }
  47.     }
  48.     //}
  49.     return mon;
  50. }
  51. signed 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.     shop_ind = 0;
  74.     mon = 0;
  75.     int ans = 0;
  76.     for (int i = 0; i <= N; i++) {
  77.         int x = produce(i);
  78.         ans = max(x + rent(min(R, N - i)), ans);
  79.     }
  80.     cout << ans << endl;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement