C. Little Girl and Maximum Sum :Codeforces

1

Can someone help me in solving this greedy problem ??

I am not able to understand the editorial .

2

I’m not sure what’s in the editorial but I think it can be solved using prefix sum. Like figuring out which index would be most important, saying which has maximum overlap count. Then just greedily assign the largest value to the index having the largest overlap count and so on. Ex:
Lets say two queries are :
1 2 and 1 3
then you can see 1 and 2 overlaps twice while 3 only once
so the count array( pref in code) would be
2 2 1

void test_case(){
	int n,q;
	cin>>n>>q;
	vector<long long> A(n);
	for(auto& x:A) cin>>x;
	if(n==1){
		cout<<q*A[0]<<"\n";
		return ;
	}
	vector<long long> pref(n,0);
	while(q--){
		int a,b;
		cin>>a>>b;
		--a;--b;
		pref[a]++;
		if(b!=n-1) pref[b+1]-=1;
	}
	for(int i=1;i<n;i++) pref[i]+=pref[i-1];
	sort(pref.rbegin(),pref.rend());
	sort(A.rbegin(),A.rend());
	long long ans=0;
	for(int i=0;i<n;i++){
		ans+=pref[i]*A[i];
	}
	cout<<ans<<"\n";
	return ;
}

If it makes sense…

2 Likes
3

Thank you bro,your explanation was brilliant .I got it .

// MY CODE

// SPIDER MAN SPIDER MAN CHURA LE MERE DIL KA CHAIN 
    #include<bits/stdc++.h>
    using namespace std;
    int n,q,l,r,i;
    long long a[200010],t[200010],f;
    int main(){
    cin.tie(0);
    cin>>n>>q;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(i=0;i<q;i++)cin>>l>>r,t[l-1]++,t[r]--;
    for(i=1;i<n;i++)t[i]+=t[i-1];
    sort(t,t+n);
    for(i=0;i<n;i++)f+=a[i]*t[i];
    cout<<f<<endl;
    }