SHARE
TWEET

Untitled

a guest Dec 14th, 2019 76 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
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