Cod sursa(job #2669629)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 7 noiembrie 2020 13:23:10
Problema Orase Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_LENGTH = 50002;

struct City{
    int position, length;
};

bool sortCity(City first, City second){
    if (first.position < second.position){
        return true;
    }else if (first.position == second.position && first.length < second.length){
        return true;
    }
    return false;
}

int main (void){
    ifstream fin ("orase.in");

    int length, toIgnore;
    fin>>toIgnore>>length;

    City city[MAX_LENGTH];

    for (int i=1; i<=length; i++){
        fin>>city[i].position>>city[i].length;
    }
    fin.close();

    for (int i=1; i<=length; i++)
        for (int j=i+1; j<=length; j++)
            if (city[i].position > city[j].position || (city[i].position == city[j].position && city[i].length > city[j].length)){
                City aux = city[j];
                city[j] = city[i];
                city[i] = aux;
            }

    int maxPath = city[1].length;
    int maxPathIndex = 1;

    int maxim = 0;

    for (int i=2; i<=length; i++){
        int aux = maxPath + city[i].position - city[maxPathIndex].position + city[i].length;
        if (aux > maxim)
            maxim = aux;

        if (city[i].length > (maxPath + city[i].position - city[maxPathIndex].position)){
            maxPath = city[i].length;
            maxPathIndex = i;
        }
    }

    ofstream fout("orase.out");
    fout<<maxim<<"\n";
    fout.close();

    return 0;
}