Codeforces Round 169 (Div. 2) 276C - Little Girl and Maximum Sum Solution

 

 Problem Link  :   https://codeforces.com/problemset/problem/276/C

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. const int mx = 2e5 + 9 ;
10. long long cnt [mx] ;
11. long long a[mx] ;
12. int32_t main(){
13. int n , q ;
14. cin >> n >> q ;
15. for ( int i = 1 ; i <= n ; i++ ) {
16. cin >> a[i] ;
17. }
18. int l , r ;
19. for ( int i = 1 ; i <= q ; i++ ) {
20. cin >> l >> r ;
21. cnt[l]++ ;
22. cnt[r+1]-- ;
23. }
24. cnt [ 0 ] = 0 ;
25. for ( int i = 1 ; i <= n ; i++ ){
26. cnt [i] += cnt[i-1] ;
27. }
28. sort ( a + 1 , a + n + 1) ;
29. sort ( cnt + 1 , cnt + n + 1) ;
30. long long ans = 0 ;
31. for ( int i = 1 ; i <= n ; i++ ){
32. ans += ( a[i] * cnt[i] ) ;
33. }
34. cout << ans << endl;
35. return 0 ;
36. }