Cod sursa(job #265442)

Utilizator vlad_DVlad Dumitriu vlad_D Data 23 februarie 2009 21:45:15
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>

using namespace std;
int n;
struct nod {
       nod(){};
       nod(int _p, int _d) {pos = _p; dist = _d;};
       int pos, dist;
       };
nod v[500001];

bool operator<(const nod &a, const nod &b) {
     if (a.pos < b.pos) return true;
     return false;
     }
int bestS = 0;

int main() {
    ifstream fin("orase.in");
    ofstream fout("orase.out");
    
    fin >> n >> n;
    
    //read
    for (int i = 1; i <= n; ++i) fin >> v[i].pos >> v[i].dist;
    
    //sortez
    sort(v+1, v + n + 1);    
    int gDist = v[1].dist;
    for (int i = 2; i <= n; ++i) {
        gDist+=v[i].pos - v[i-1].pos;
        if (gDist + v[i].dist > bestS) bestS = gDist + v[i].dist;
        if (v[i].dist > gDist) gDist = v[i].dist;
       
        }        
    fout << bestS << '\n';        
    return 0;
    }