Cod sursa(job #2672318)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 13 noiembrie 2020 17:20:18
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 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;
    }
    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();
 
    sort(city+1, city+length+1, sortCity);
 
    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;
}