Triathlon, INOI 2012

Problem Description

Question : Triathlon, INOI 2012

Submit Code : Codechef

Prerequisites

Sorting

Solution

The question is very lengthy, but easy once understood. We have given time taken by each citizen in the events consisting of three (COBOL, Pole vault, and Doughnut-eating). Where COBOL being a programming event will be participated by citizen one after another (as there is only one computer). Also, a citizen has to first participate in COBOL, then Pole vault and then Doughnut-eating. So, citizen need to wait for other citizen in COBOL event but once COBOL event is completed they can participate in other two events without waiting for anyone. We have to reduce the time taken by citizen to finish all events by ordering them in a sequence.

We will go as follow:

1. We can merge the time taken by citizens for Pole vault and Doughnut-eating as it doesn't depend on other citizens.
2. We can observe that time taken to complete COBOL will increase as citizens participate, because other citizens have to wait till the current zitizen finish the event. So, whatever be the order in which citizen participate the COBOL programming event will take same amount of time.
3. We can see that if we order the citizens combined evets (Pole vault + Doughnut-eating) time in descending order. Then it will reduce the time took to finsh the whole event.
4. So, we will sort events time in descending in pair as (Pole vault + Doughnut-eating, COBOL) to get the answer.

Code

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> time;
    int cobol, pole, doughnut;

    for(int i=0;i<n;i++){
        cin >> cobol >> pole >> doughnut;
        time.push_back(make_pair(pole + doughnut, cobol));
    }

    sort(time.begin(), time.end(), greater<pair<int, int>>());
    
    int sum = 0, ans = 0;
    for(int i=0;i<n;i++){
        sum += time[i].second;
        ans = max(ans, sum + time[i].first);
    }
    cout << ans;

    return 0;
}