Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- int pref[100001], pref2[100001];
- vector<int> c(100000);
- vector<pair<int, int> > shops(100000);
- vector<int> farms(100000);
- bool comp(pair<int, int> p, pair<int, int> q) {
- return p.second > q.second;
- }
- int rent(int i) {
- return pref[i];
- }
- void setIO(string s) {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen((s + ".in").c_str(), "r", stdin);
- freopen((s + ".out").c_str(), "w", stdout);
- }
- int produce(int cow) {
- vector<pair<int, int> > shops2(100000);
- for(int i = 0; i < 100000; ++i) {
- shops2[i] = shops[i];
- }
- int prefsum = pref2[cow];
- int mon = 0;
- int shop_ind = 0;
- //for (int cow = 0; cow < 100000; cow++) {
- while (shops2[shop_ind].first > 0) {
- int sell = min(prefsum, shops2[shop_ind].first);
- prefsum -= sell;
- shops2[shop_ind].first -= sell;
- mon += sell * shops2[shop_ind].second;
- if (shops2[shop_ind].first == 0) {
- shop_ind++;
- }
- if (prefsum == 0) {
- break;
- }
- }
- //}
- return mon;
- }
- int main() {
- setIO("rental");
- int N, M, R;
- cin >> N >> M >> R; //cows, stores, neighbors
- for (int i = 0; i < N; i++) {
- cin >> c[i];
- }
- sort(c.rbegin(), c.rend());
- for(int i = 1; i <= N; ++i) {
- pref2[i] = pref2[i - 1] + c[i - 1];
- }
- for (int i = 0; i < M; i++) {
- cin >> shops[i].first >> shops[i].second;
- }
- sort(shops.begin(), shops.end(), comp);
- for (int i = 0; i < R; i++) {
- cin >> farms[i];
- }
- sort(farms.rbegin(), farms.rend());
- for(int i = 1; i <= R; ++i) {
- pref[i] = pref[i - 1] + farms[i - 1];
- }
- int ans = 0;
- for (int i = 0; i <= min(N, R); i++) {
- ans = max(produce(N - i) + rent(i), ans);
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement