THESELEC - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Simple

PREREQUISITES:

Basic Maths, Sorting, Greedy

PROBLEM:

You are given N integers A_1,A_2,...,A_N. You are also given Q queries. Each query i (1\leq i\leq Q) is of the type L_i R_i X_i: meaning, add the value X_i to all the integers in the array whose indices lie in the range [L_i,R_i].

Your task is to tell the maximum possible sum of all the elements of the array if you are allowed to choose at most K (\leq Q) queries among the given queries.

QUICK EXPLANATION:

The answer is (sum of all the array elements) + (largest positive val_i's (maximum K val_i's)), where val_i = X_i*(R_i-L_i+1).

EXPLANATION:

Notice that the answer cannot be less than the sum of all the elements of the array. It is because we can decide not to choose any queries. So the answer is always greater than or equal to \sum_{i=1}^{N} A_i.

Now, let val_i = X_i*(R_i-L_i+1) represent the value of the i^{th} query. val_i represents the amount query i will add to the array. Why so? Because X_i is added (R_i-L_i+1) number of times to the array. It is now obvious that we will only choose those queries that have a positive value, because if we choose a query having a negative value, it will reduce our sum.

So our answer now becomes (sum of all the array elements) + (largest positive val_i's (maximum K val_i's)).

Now try to implement the approach on your own. Refer to the solutions below for implementation details if you are facing difficulties.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()

using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input5.txt","r",stdin);
    // freopen("output5.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n,q,k,ans=0,i;
        cin>>n>>q>>k;
        ll a[n+10];
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
            ans+=a[i];
        }
        vector<ll> v;
        while(q--)
        {
            ll l,r,x;
            cin>>l>>r>>x;
            ll val=x*(r-l+1);
            v.pb(val);
        }
        sort(rall(v));
        for(i=0;i<k;i++)
        {
            if(v[i] > 0)
                ans+=v[i];
            else break;
        }
        cout<<ans<<"\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int t;
  cin>>t;
  
  while(t--)
  {
    int n,q,k;
    cin>>n>>q>>k;
    
    long long a[n],tot=0;
 
    for(int i=0;i<n;i++){
      cin>>a[i];
      tot+=a[i];
    }
 
    vector<long long> vals;
    while(q--)
    {
      long long l,r,x;
      cin>>l>>r>>x;
 
      if((r-l+1)*x>0)
        vals.push_back((r-l+1)*x);
    }
 
    sort(vals.begin(), vals.end());
    reverse(vals.begin(), vals.end());
 
    int cnt=0;
    for(auto x:vals)
    {
      if(cnt>=k)break;
      cnt++;
      tot+=x;
    }
    
    cout<<tot<<"\n";
  }
  return 0;
}

Feel free to write your approach in the comments :slight_smile:

3 Likes