Pagini recente » Cod sursa (job #1769193) | Cod sursa (job #848243) | Cod sursa (job #2672929)
#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;
}