fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll INF = -4e18;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, k;
  11.     cin >> n >> k;
  12.     vector<ll> A(n), B(n);
  13.     for (auto &x : A) cin >> x;
  14.     for (auto &x : B) cin >> x;
  15.  
  16.     vector<ll> dp0(k+1, INF), dp1(k+1, INF);
  17.     ll ans = -INF;
  18.  
  19.     for (int i = 0; i < n; i++) {
  20.         vector<ll> new0(k+1, INF), new1(k+1, INF);
  21.         for (int j = 0; j <= k; j++) {
  22.             ll a = A[i], b = B[i];
  23.  
  24.             // Không trong đoạn nhân
  25.             new0[j] = a;
  26.             if (dp0[j] != INF) new0[j] = max(new0[j], dp0[j] + a);
  27.             if (dp1[j] != INF) new0[j] = max(new0[j], dp1[j] + a);
  28.  
  29.             // Trong đoạn nhân
  30.             if (j > 0) {
  31.                 new1[j] = a * b;
  32.                 if (dp1[j] != INF) new1[j] = max(new1[j], dp1[j] + a * b);
  33.                 if (dp0[j-1] != INF) new1[j] = max(new1[j], dp0[j-1] + a * b);
  34.             }
  35.  
  36.             ans = max({ans, new0[j], new1[j]});
  37.         }
  38.         dp0.swap(new0);
  39.         dp1.swap(new1);
  40.     }
  41.  
  42.     cout << ans;
  43. }
  44.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
5 1
-3 4 -5 2 -2
1 -2 -1 2 1
stdout
copy 
4000000000000000000
https://ideone.com/IjrVhD
language:
C++14 (gcc 8.3)
created:
3 days 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!