Cod sursa(job #2672929)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 15 noiembrie 2020 14:45:55
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
 
const int MAX_LENGTH = 50002;
 
struct City{
    int position, length;
};
 
void merge (City array[], int left, int middle, int right){
    int leftLength = middle - left + 1;
    int rightLength = right - middle;

    City leftArray[leftLength + 1], rightArray[rightLength + 1];

    int leftIndex, rightIndex, index;

    if (leftLength < rightLength)
        index = leftLength;
    else
        index = rightLength;

    for (leftIndex = 1, rightIndex = 1; index > 0; leftIndex++, rightIndex++, index--){
        leftArray[leftIndex] = array[left + leftIndex - 1];
        rightArray[rightIndex] = array[middle + rightIndex];
    }

    for (; leftIndex <= leftLength; leftIndex++)
        leftArray[leftIndex] = array[left + leftIndex - 1];

    for (; rightIndex <= rightLength; rightIndex++)
        rightArray[rightIndex] = array[middle + rightIndex];

    leftIndex = 1, rightIndex = 1, index = 0;

    while (leftIndex <= leftLength && rightIndex <= rightLength){
        if (leftArray[leftIndex].position < rightArray[rightIndex].position){
            array[left + index] = leftArray[leftIndex];
            leftIndex++;
        }else
        {
            array[left + index] = rightArray[rightIndex];
            rightIndex++;
        }
        
        index++;
    }

    for (; leftIndex <= leftLength; leftIndex++, index++)
        array[left + index] = leftArray[leftIndex];

    for (; rightIndex <= rightLength; rightIndex++, index++)
        array[left + index] = rightArray[rightIndex];
}

void mergeSort (City array[], int left, int right){
    if (left < right){

        int middle = left + right;
        middle /= 2;

        mergeSort (array, left, middle);
        mergeSort (array, middle + 1, right);

        merge(array, left, middle, right);
    }

}
 
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();
 
    mergeSort(city, 1, length);
 
    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;
}