BBCANDY2 - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t

DIFFICULTY:

Easy - Medium

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
  • You can maintain a dp array where dp[i] = max sweetness possible for candies from 1 to i if you buy the i_{th} candy

Base case dp[1] = A[i]
Progression rule dp[i] = A[i]+ max(\forall _{j \in [i-R,i-L]} dp[j])

Subtask 1:

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

Time complexity:

O(N^2)

Subtask 2:

To find maximumm of each window maintain a map of dp values and at each pass remove the dp[i-R-1] from map and add dp[i-L] th cost to map. Maximum at each pass is the last element in map. This can be found in O(logN) for each i
Do this for all i (1 \leq i \leq N).
Find max of all values found.

Time complexity:

O(N*logN)

SOLUTION

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	// your code goes here
	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;
    vector<ll> dp(n);
		ll ans=0;
		for(int i=0;i<n;i++){
			if(i-r-1>=0){
				mp[dp[i-r-1]]--;
				if(mp[dp[i-r-1]]==0){
					auto it =mp.find(dp[i-r-1]);
					mp.erase(it);
				}
			}
			if(i-l>=0){
				mp[dp[i-l]]++;
			}
      ll temp=0;
			if(mp.size()){
				auto it =mp.end();
        it--;
				temp=it->first;
			}
      dp[i]=temp+a[i];
      ans=max(ans,dp[i]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}