PROBLEM LINK:
Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318
DIFFICULTY:
Hard
PREREQUISITES:
Dynamic Programming
PROBLEM:
Choose K disjoint distinct subarrays each of length L from an array of size N such that their sum is maximum. Also, you are allowed to choose at most C elements twice in a subarray.
EXPLANATION:
Let’s choose K subarrays one by one. For choosing xth subarray suppose we already have best possible answer for 0 common element, 1 common element …C common elements for each array from [0, i] for x-1 subarrays. Now if we want to choose xth subarray from [i+1,i+L] then:
For 0 common elements with subarray [i+1, i+L] best possible ans is: max( ans for x-1th subarray till i such that C elements are common, ans for x-1th subarray till i such that C-1 elements are common…, ans for x-1th subarray till i such that 0 elements are common) + sum of subarray [i+1, i+L].
Similarly, for 1 common elements with subarray [i+1,i+L] best possible ans is: max( ans for x-1th subarray till i+1 such that C-1 elements are common, ans for x-1th subarray till i+1 such that C-2 elements are common…, ans for (x-1)th subarray till i+1 such that 0 elements are common) + sum of subarray [i+1, i+L].
Similarly, we can choose best answer with subarray [i+1,i+L] for 2 commons,3 commons…C commons.
Now, in the same way, we can find best solution for K subarrays.
For formally,
Dp[Nth][last\_index\_of\_subarray][Cth\_common] = max(Dp[(N-1)th][last\_index\_of\_subarray -L+ Cth\_common][C- Cth\_common] + sum\_of\_subarray[last\_index\_of\_subarray - L+1,last\_index\_of\_subarray], X)
where,
- Dp[i][j][k] denotes best answer for choosing ith subarray(0 \leq i \leq K) till jth index and for k commons.
- sum\_of\_subarray[i,j] is the sum of subarray in range [i,j] (0 \leq i \leq j \leq N-1)
- X = max(Dp[Nth][last\_index\_of\_subarray-1][Cth\_common], Dp[Nth][last\_index\_of\_subarray][Cth\_common-1])
TIME COMPLEXITY:
O(N*K*C)
SOLUTIONS:
Solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v,i) v.begin()+i,v.end()
#define en "\n"
#define mem(a,b) memset(a,b,sizeof(a));
#define F first
#define S second
#define mod 1000000007
#define mod2 998244353
typedef long long int ll;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int T = 1, I;
cin >> T;
for (I = 1; I <= T; I++) {
ll n, k, l, i, j, o, c;
cin >> n >> k >> l >> c;
ll a[n + 1], pre[n + 1];
pre[0] = 0;
for (i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
if ((k * l - ((k / 2)*c)) > n) {
cout << -1 << en;
continue;
}
vector<vector<ll>> dp(n + 1, vector<ll> (c + 1));
ll ans = 0;
for (i = 1; i <= k; i++) {
vector<vector<ll>> dp1(n + 1, vector<ll> (c + 1));
for (j = l; j <= n; j++) {
for (o = 0; o <= c; o++) {
dp1[j][o] = max(dp[j - l + o][c - o] + pre[j] - pre[j - l], dp1[j - 1][o]);
if (o > 0)
dp1[j][o] = max(dp1[j][o], dp1[j][o - 1]);
}
}
dp = dp1;
}
for (i = 1; i <= n; i++)for (j = 0; j <= c; j++)ans = max(ans, dp[i][j]);
cout << ans << en;
}
return 0;
}