**PROBLEM LINKS**:

Practice Contest

**Editorialist**: hackxsaras

**DIFFICULTY**:

Sorting, STL, Dynamic Programming

**PROBLEM** (in short):

There are * N citizens* participating in an event. The event has

*(say*

**3**tracks**A,B,C**in order). Each participant has to do all the three tracks in the same order. More than one participants can do

*and*

**B***simultaneously whereas*

**C***has to be done separately. We can alter the order in which participants appear in the event ( order of tracks remaining same ).*

**A**Given, the time required by each of the participants for each track. Calculate the minimum time in which the whole event could be completed.

For example, suppose **N** = 3, and the time they need for the three tracks are as follows:

If the citizens start at time **0** and proceed in the order **1,2,3**, then citizen 1 will finish at time **18+7+6 = 31**, citizen **2** will finish at time **18 + (23+10+27) = 78**, and citizen **3** will finish at time **18+23 + (20+9+14) = 84**. The event ends at time **max(31,78,84)=84**. (this is not the optimal solution)

**EXPLANATION**:

Now with keen observation, we could establish a fact that if we arrange the citizens according to the sum of time of the tracks **B** and **C** in reverse order, the time is minimised. In the above example the order would be **2, 3,1** because (10+27) > (9+14) > (7+6) and **Time to complete event = 74**.

So, We have to use a comparator which will sort the citizens according to the sum of B and C in decreasing order [ O(**N** **log****N**) ] and then just calculate the time required to complete the event [O(**N**)].

**TIME COMPLEXITY**:

O(**N** **log****N**) (as disussed above)

**SOLUTION**:

## If above link is dead

```
#include <bits/stdc++.h>
using namespace std;
#define tc int t;cin>>t;while(t--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff(i,a,b) for(int i=a;i<b;i++)
#define fb(i,b,a) for(int i=b;i>a;i--)
#define ffi(i,a,b,c) for(int i=a;i<b;i+=c)
#define fbi(i,b,a,c) for(int i=b;i>a;i-=c)
#define clin(s) getline(cin,s)
#define MOD 1e9+7
#define pb push_back
#define mp make_pair
#define all(var) var.begin(),var.end()
bool comp(vector<int> a,vector<int> b){
return (a[2]+a[1])>(b[2]+b[1]);
}
int main() {
int n;
cin>>n;
vector<vector<int>> tri;
ff(i,0,n){
int a,b,c;
cin>>a>>b>>c;
tri.pb({a,b,c});
}
sort(all(tri),comp);
int cobol=0,spent=0;
for(int i=0;i<n;i++){
cobol+=tri[i][0];
spent=max(spent,cobol+tri[i][1]+tri[i][2]);
}
cout<<spent<<"\n";
return 0;
}
```

Thank You for Reading