Advertisement
he_obviously

Untitled

May 24th, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. const int SZ = 4e3 + 4;
  9.  
  10. int n, m, c;
  11. vector<int> a[SZ];
  12. int s[SZ];
  13. int b[SZ];
  14. int sum = 0;
  15.  
  16. bool comp(int x, int y) {
  17.     return x > y;
  18. }
  19.  
  20. int main() {
  21.  
  22.     ios_base::sync_with_stdio(0);
  23.     cin.tie(0); cout.tie(0);
  24.  
  25.     cin >> n >> m >> c;
  26.     vector<int> t(n);
  27.     for (int i = 0; i < n; ++i) {
  28.         cin >> t[i];
  29.         --t[i];
  30.     }
  31.     for (int i = 0; i < n; ++i) {
  32.         int x;
  33.         cin >> x;
  34.         a[t[i]].push_back(x);
  35.         s[t[i]] += x;
  36.         sum += x;
  37.     }
  38.     for (int i = 0; i < m; ++i) {
  39.         cin >> b[i];
  40.     }
  41.  
  42.      for (int i = 0; i < m; ++i) {
  43.         sort(a[i].begin(), a[i].end(), comp);
  44.         for (int j = 0; j < a[i].size(); ++j) {
  45.             if (j) a[i][j] += a[i][j - 1];
  46.             if (j + 1 >= b[i]) {
  47.                 a[i][j] = s[i];
  48.             }
  49.         }
  50.     }
  51.  
  52.     vector<int> dp(c + 1, -1);
  53.     dp[0] = 0;
  54.     for (int i = 0; i < m; ++i) {
  55.         for (int j = c; j >= 1; --j) {
  56.             for (int k = 0; k < a[i].size(); ++k) {
  57.                 if (k + 1 <= j && dp[j - k - 1] != -1) {
  58.                     dp[j] = max(dp[j], dp[j - k - 1] + a[i][k]);
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     int ans = 0;
  64.     for (int i = 0; i <= c; ++i) {
  65.         ans = max(ans, dp[i]);
  66.     }
  67.  
  68.     cout << sum - ans << "\n";
  69.  
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement