Guest User

Untitled

a guest
Mar 9th, 2019
275
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(0);
  9.     cin.tie(0);
  10.     int n, m, k;
  11.     cin >> n >> m >> k;
  12.     vector <int> p(n);
  13.     for (int i = 0; i < n; i++) {
  14.         cin >> p[i];
  15.     }
  16.     vector <int> b(m + 1);
  17.     for (int i = 0; i <= m; i++) {
  18.         cin >> b[i];
  19.     }
  20.     vector <ll> dp(k + 1, 0);
  21.     for (int i = 0; i < n; i++) {
  22.         vector <ll> go(k + 1, 0);
  23.         for (int j = 0; j <= k; j++) {
  24.             for (int x = 0; x <= k; x++) {
  25.                 if (x > j) break;
  26.                 int add = j - x;
  27.                 if (p[i] + add > m) continue;
  28.                 go[j] = max(go[j], dp[x] + b[p[i] + add]);
  29.             }
  30.         }
  31.         dp = go;
  32.     }
  33.     ll ans = 0;
  34.     for (int i = 0; i <= k; i++) {
  35.         ans = max(ans, dp[i]);
  36.     }
  37.     cout << ans << '\n';
  38.     return 0;
  39. }
Add Comment
Please, Sign In to add comment