Problem link
Author: ryuusama
Tester: sayan_244, dhrub_kumar, omniking
Editorialist: dedsec_29
Difficulty
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;
}