fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, K;
  11.     if (!(cin >> n >> K)) return 0;
  12.  
  13.     vector<ll> A(n), B(n);
  14.     for (int i = 0; i < n; ++i) cin >> A[i];
  15.     for (int i = 0; i < n; ++i) cin >> B[i];
  16.  
  17.     vector<unordered_map<ll, ll>> dp(K + 1);
  18.     dp[0][0] = 0;
  19.  
  20.     auto relax = [](unordered_map<ll, ll>& M, ll key, ll val) {
  21.         auto it = M.find(key);
  22.         if (it == M.end() || val > it->second) M[key] = val;
  23.     };
  24.  
  25.     for (int i = 0; i < n; ++i) {
  26.         ll t = A[i] + B[i];
  27.         ll d = A[i] - B[i];
  28.  
  29.         vector<unordered_map<ll, ll>> nxt = dp;
  30.         int up = min(K, i + 1);
  31.  
  32.         for (int j = 1; j <= up; ++j) {
  33.             for (const auto& kv : dp[j - 1]) {
  34.                 ll Dnew = kv.first + d;
  35.                 ll Tnew = kv.second + t;
  36.                 relax(nxt[j], Dnew, Tnew);
  37.             }
  38.         }
  39.         dp.swap(nxt);
  40.     }
  41.  
  42.     if (dp[K].empty()) {
  43.         cout << 0;
  44.         return 0;
  45.     }
  46.  
  47.     ll ans = LLONG_MIN;
  48.     for (const auto& kv : dp[K]) {
  49.         ll D = kv.first, T = kv.second;
  50.         ans = max(ans, (T - llabs(D)) / 2);
  51.     }
  52.     cout << ans;
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FXap8D
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!