﻿

# Untitled

a guest
Dec 14th, 2019
87
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4. typedef long long ll;
5.
6. int n, m;
7. vector<int> a;
8. vector<pair<int, int>>b;
9. ll f(int d){
10.     vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(n+1, vector<ll> (m+1)));
11.     vector<vector<vector<ll>>> dp2(2, vector<vector<ll>>(n+1, vector<ll>(m+1)));
12.     dp[0][0][0] = dp[1][0][0] = 10000;
13.     for (int j = 1; j <= m; ++j){
14.         dp[1][0][j] = dp[1][0][j-1] - b[j].second;
15.         dp2[1][0][j] = dp[1][0][j-1]*b[j].first + dp2[1][0][j-1];
16.     }
17.     for (int i = 1; i <= n; ++i){
18.         dp[0][i][0] = dp[0][i-1][0] + a[i];
19.         dp2[0][i][0] = dp2[0][i-1][0];
20.     }
21.     for (int i = 1; i <= n; ++i){
22.         for (int j = 0; j <= m; ++j){
23.             if (j == 0){
24.                 dp[0][i][j] = max(dp[0][i-1][j], dp[1][i-1][j]) + a[i];
25.                 dp2[0][i][j] = max(dp2[0][i-1][j], dp2[1][i-1][j]);
26.             }
27.             else {
28.                 dp[0][i][j] = max(dp[0][i-1][j], dp[1][i-1][j]) + a[i];
29.                 dp[1][i][j] = max(dp[0][i][j-1], dp[1][i][j-1]) - b[j].second;
30.                 dp2[0][i][j] = max(dp2[0][i-1][j], dp2[1][i-1][j]);
31.                 if (dp2[1][i][j - 1] + dp[1][i][j - 1] * b[j].first >
32.                     dp2[0][i][j-1] + dp[0][i][j-1] * b[j].first) {
33.                     dp2[1][i][j] = dp2[1][i][j - 1] + dp[1][i][j - 1] * b[j].first;
34.                 } else dp2[1][i][j] = dp2[0][i][j-1] + dp[0][i][j-1] * b[j].first;
35.             }
36.         }
37.     }
38.     ll ma = 0;
39.     for (int i = 0; i <= n; ++i){
40.         if (d-i <= m && d-i >= 0){
41.             ma = max({ma, dp2[0][i][d-i], dp2[1][i][d-i]});
42.         }
43.     }
44.     return ma;
45. }
46. int main() {
47.     iostream::sync_with_stdio(false); cout.tie(0); cin.tie(0);
48.     cin >> n;
49.     a.resize(n+1);
50.     for (int i = 1; i <= n; ++i)
51.         cin >> a[i];
52.     cin >> m;
53.     b.resize(m+1);
54.     for (int i = 1; i <= m; ++i){
55.         cin >> b[i].first >> b[i].second;
56.     }
57.     sort(a.begin(), a.end(), [](ll p1, ll p2){
58.         if (p1 == 0) return true;
59.         else if (p2 == 0) return false;
60.         return p1 > p2;
61.     });
62.     int q; cin >> q;
63.     auto t = b;
64.     while (q--){
65.         int d; cin >> d;
66.
67.         ll ma = f(d);
68.         while(next_permutation(t.begin(), t.end())){
69.             b = t;
70.             for (int i = 0; i < m; ++i){
71.                 if (b[i] == make_pair(0, 0)) {
72.                     swap(b[0], b[i]);
73.                     break;
74.                 }
75.             }
76.             ma = max(ma, f(d));
77.         }
78.         cout << ma << '\n';
79.     }
80.     return 0;
81. }
RAW Paste Data