SHARE
TWEET

Untitled

a guest Aug 18th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define F first
  5. #define S second
  6. typedef pair<int, int> ii;
  7. typedef vector<int> vi;
  8. inline ll gi() {
  9.     ll x=0,f=1;
  10.     char ch=getchar();
  11.     while(!isdigit(ch))f^=ch=='-',ch=getchar();
  12.     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
  13.     return f?x:-x;
  14. }
  15. bool sortp(const vector<int> &a, const vector<int> &b) {
  16.     return a[1]<b[1];
  17. }
  18. int milk[100005], msuffix[100005], rent[100005], rsuffix[100005];
  19. vector<vi> store;
  20. int main() {
  21. #ifndef HOME
  22.     freopen("rental.in", "r", stdin);
  23.     freopen("rental.out", "w", stdout);
  24. #endif
  25.     int n=gi(), m=gi(), r=gi();
  26.     for(int i=0; i<n; i++) milk[i]=gi();
  27.     for(int i=0; i<m; i++) {
  28.         vi s;
  29.         for(int j=0; j<2; j++) s.push_back(gi());
  30.         store.push_back(s);
  31.     }
  32.     for(int i=0; i<r; i++) rent[i]=gi();
  33.     sort(milk, milk+n);
  34.     sort(store.begin(), store.end(), sortp);
  35.     sort(rent, rent+r);
  36.     for(int i=n-1; i>=0; i--)
  37.         msuffix[i]=i==n-1?milk[i]:milk[i]+msuffix[i+1];
  38.     for(int i=r-1; i>=0; i--)
  39.         rsuffix[i]=i==r-1?rent[i]:rent[i]+rsuffix[i+1];
  40.     ll ans=0;
  41.     for(int i=0, j=1; i<n-1&&j<n; i++, j++) {
  42.         ll ans1=0;
  43.         int milkamt=msuffix[j];
  44.         for(int k=m-1; k>=0; k--) {
  45.             if(milkamt-store[k][0]>0) {
  46.                 milkamt-=store[k][0];
  47.                 ans1+=store[k][0]*store[k][1];
  48.             } else {
  49.                 ans1+=store[k][1]*milkamt;
  50.                 break;
  51.             }
  52.         }
  53.         ans1+=rsuffix[(r-1)-(i+1)+1];
  54.         ans=max(ans1, ans);
  55.     }
  56.     printf("%d\n", ans);
  57.     return 0;
  58. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top