# DAFF69 - Editorial

Author: ryuusama
Tester: sayan_244, dhrub_kumar, omniking
Editorialist: dedsec_29

Medium

# Prerequisites:

Dynamic Programming (DP)

# Quick Explanation

We can use dynamic programming with states (Number of flowers seen so far, number of flowers chosen so far, number of modifications modified so far)

# Explanation

Define \text{dp}[i][k][d] as, the maximum Hanna power possible if we choose the i^{th} flower and we have chosen k flowers so far and have performed d modifications.

Define \text{RMQ[i][j]} as the range maximum query in the interval [i..j] (inclusive)
Define \text{rmq}[i][j] as the range minimum query in the interval [i..j] (inclusive)

Define \text{util}[i][j][c] as the maximum value of \text{RMQ}[i][j] - \text{rmq}[i][j] by making exactly c modifications in the interval [i..j].

Then,

\text{RMQ}[i][j] = \max_{i \leq k \leq j} a_k
\text{rmq}[i][j] = \min_{i \leq k \leq j} a_k

\text{dp}[i][k][d] = \max_{0 \leq j \lt i}\max_{0 \leq c \leq i-j}(\text{dp}[j][k-1][d-c] + \text{util}[j+1][i][c])

considering 0-based indexing.

Calculating dp[i][k][d] by considering all values of c will certainly not fit in the time limit. So how do we optimize it?

We can make the observation that in any interval [i..j], to maximize the value of \text{RMQ}[i][j] - \text{rmq}[i][j], we will at most need 2 modifications. This is because with 1 modification, an element a_k may become the maximum in the interval, and with another modification, an element may become the minimum in the interval. Hence we should consider only the values 0, 1 and 2 for c.

We can pre-compute \text{RMQ}[i][j] in O(n^2) time and \text{rmq}[i][j] in O(n^2) time, using which we can pre-compute, \text{util[i][j][0]} in O(n^2) time, \text{util[i][j][1]} in O(n^3) time and \text{util}[i][j][2] in O(n^4) time.

Using all these pre-computations, we can find the \text{dp} values in O(n^4) time, which is enough to fit in the time limit.

The final answer is now simply \max_{1 \leq i \leq N, 0 \leq d \leq D} \text{dp}[i][K][d]

# Solutions

Setter's solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize "trapv"
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#pragma GCC optimize("unroll-loops")
#define int long long

int const inf = 1e18;

void solve() {
int N,K,D; cin >> N >> K >> D;
vector<int> a(N), b(N);
vector<vector<vector<int>>> dp(N, vector<vector<int>>(K+1, vector<int>(D+1, -inf)));
for (int& i: a) cin >> i;
for (int& i: b) cin >> i;

vector<vector<int>> util1(N, vector<int>(N, -inf));
vector<vector<int>> util2(N, vector<int>(N, -inf));
vector<vector<int>> RMQ(N, vector<int>(N));
vector<vector<int>> rmq(N, vector<int>(N));
for (int i = 0; i < N; i++) {
RMQ[i][i] = a[i], rmq[i][i] = a[i];
for (int j = i+1; j < N; j++) {
RMQ[i][j] = max(RMQ[i][j-1], a[j]);
rmq[i][j] = min(rmq[i][j-1], a[j]);
}
}

// [l...u...r]
for (int l = 0; l < N; l++) {
for (int r = l; r < N; r++) {
for (int u = l; u <= r; u++) {
int A = max({a[u] + b[u], (u == l) ? -inf : RMQ[l][u-1], (u == r) ? -inf : RMQ[u+1][r]});
int B = min({a[u] + b[u], (u == l) ? inf : rmq[l][u-1], (u == r) ? inf : rmq[u+1][r]});
util1[l][r] = max(util1[l][r], A-B);
}
}
}
// [l..u..v..r]
for (int l = 0; l < N; l++) {
for (int r = l; r < N; r++) {
for (int u = l; u <= r; u++) {
for (int v = u+1; v <= r; v++) {
int A = max(a[u] + b[u], a[v] + b[v]);
A = max(A, (u == l) ? -inf : RMQ[l][u-1]);
A = max(A, (u+1 == v) ? -inf : RMQ[u+1][v-1]);
A = max(A, (v == r) ? -inf : RMQ[v+1][r]);

int B = min(a[u] + b[u], a[v] + b[v]);
B = min(B, (u == l) ? inf : rmq[l][u-1]);
B = min(B, (u+1 == v) ? inf : rmq[u+1][v-1]);
B = min(B, (v == r) ? inf : rmq[v+1][r]);
util2[l][r] = max(util2[l][r], A-B);
}
}
}
}

for (int i = 0; i < N; i++) {
for (int k = 0; k <= min(i+1, K); k++) {
for (int d = 0; d <= min(i+1, D); d++) {
if (k < 2) {
dp[i][k][d] = 0;
continue;
}

for (int j = 0; j < i; j++) {
int A = dp[j][k-1][d] + RMQ[j+1][i] - rmq[j+1][i];
int B = (d <= 0) ? -inf : (dp[j][k-1][d-1] + util1[j+1][i]);
int C = (d <= 1) ? -inf : (dp[j][k-1][d-2] + util2[j+1][i]);
dp[i][k][d] = max({dp[i][k][d], A, B, C});
}
}
}
}

int ans = -inf;
for (int i = K-1; i < N; i++)
for (int j = 0; j <= D; j++)
ans = max(ans, dp[i][K][j]);

cout << ans << "\n";
}

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--)
solve();
return 0;
}

Tester's solution
// #define _GLIBCXX_DEBUG 1
// #define _GLIBCXX_DEBUG_PEDANTIC 1
// #define _FORTIFY_SOURCE 2

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
#define plli pair<lli,lli>
#define pb push_back
#define fir first
#define sec second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
constexpr lli mod=(1000*1000*1ll*1000)+7;
// constexpr lli mod=998244353;
constexpr lli inf=4ll*(((1000*1000*1ll*1000)*(1000*1000*1ll*1000))+50);
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<lli,null_type,less<lli>, rb_tree_tag,tree_order_statistics_node_update>
// remove _equal from less_equal to make it ordered set , currently it is ordered_multiset

// lli powermod(lli a, lli b,lli mod)
// {
//     lli res = 1;
//     while (b > 0) {
//         if (b & 1)
//             res = ((res%mod)*(a%mod))%mod;
//         a = (a * a)%mod;
//         b >>= 1;
//     }
//     return res%mod;
// }

// used for custom hashing in unordered_map , unordered_set
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};

using vl=vector<lli>;
using vvl=vector<vl>;
using vvvl=vector<vvl>;

constexpr lli N=110;
vvvl dp(N,vvl(N,vl(N,-inf)));
vl a,b;
lli n,cnt=0;

lli solve(lli ind,lli k,lli d){
cnt++;
if(k==0 and d>=0)
return dp[ind][k][d]=0;
if(ind==n or d<0)
return -inf;
if(dp[ind][k][d]!=-inf)
return dp[ind][k][d];
lli ans=-inf;
lli min0=inf,max0=-inf,min1=inf,max1=-inf;
for(lli i=ind;i<n;i++){
// if(a[i]+b[i]>=min0)
ans=max(ans,solve(i+1,k-1,d-1)+(a[i]+b[i]-min0));
// if(a[i]+b[i]<=max0)
ans=max(ans,solve(i+1,k-1,d-1)+(max0-a[i]-b[i]));
// if(a[i]>=min1)
ans=max(ans,solve(i+1,k-1,d-1)+(a[i]-min1));
// if(a[i]<=max1)
ans=max(ans,solve(i+1,k-1,d-1)+(max1-a[i]));
min1=min(min1,a[i]+b[i]);
max1=max(max1,a[i]+b[i]);
min0=min(min0,a[i]);
max0=max(max0,a[i]);
ans=max(ans,solve(i+1,k-1,d)+max0-min0);
ans=max(ans,solve(i+1,k-1,d-2)+max1-min1);
}
return dp[ind][k][d]=ans;
}

int main(){
fastio
lli T,i=0,j;
T=1;
cin>>T;
// assert(T>=1 and T<=100);
lli sumn=0;
while(T--){
lli k,d;
cin>>n>>k>>d;
sumn+=n;
// assert(n>=1 and n<=100 and k>=2 and k<=100 and d>=0 and d<=100);
a.resize(n);
for(i=0;i<n;i++){
cin>>a[i];
// assert(a[i]>=0 and a[i]<=mod-7);
}
b.resize(n);
for(i=0;i<n;i++){
cin>>b[i];
// assert(b[i]>=-mod+7 and b[i]<=mod-7);
}
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
for(lli l=0;l<=n;l++)
dp[i][j][l]=-inf;
lli ans=-inf;
for(i=1;i<n;i++)
ans=max(ans,solve(i,k-1,d));
cout<<ans<<"\n";
}
// assert(sumn<=100 and sumn>=1);
cerr<<"XX"<<cnt<<"\n";
return 0;
}