# BBCANDY - Editorial

Contest

Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t

Easy

# PREREQUISITES:

Window sliding, map

# Explanation:

### Observation:

• If you buy the i_{th} then you should buy the other candy with minimum cost in the window [i-R, i-L] for optimum solution
• Answer will be the minimum of cost for each such i.

Make an array of each window and find minimum of each window in O(N) and do this for all i (1 \leq i \leq N).

### Time complexity:

O(N^2)

To find minimum of each window maintain a map of cost of candies and at each pass remove the i-R-1 th cost and add i-L th cost to map. Minimum at each pass is the first element in map. In O(logN)
Do this for all i (1 \leq i \leq N).

O(N*logN)

# SOLUTION

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll T;
cin>>T;
while(T--){
ll n,l,r;
cin>>n>>l>>r;
vector<ll> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
map<ll,ll> mp;
ll ans=1e9;
for(int i=0;i<n;i++){
if(i-r-1>=0){
mp[a[i-r-1]]--;
if(mp[a[i-r-1]]==0){
auto it =mp.find(a[i-r-1]);
mp.erase(it);
}
}
if(i-l>=0){
mp[a[i-l]]++;
}
if(mp.size()){
auto it =mp.begin();
ans=min(ans,it->first+a[i]);
}
}
cout<<ans<<"\n";
}
return 0;
}