Cod sursa(job #1851900)

Utilizator isa_edi_cristeaEdi Cristea isa_edi_cristea Data 20 ianuarie 2017 11:42:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int i, j, n, m, x, k;
struct concert{
int x, y, val;
};
concert v[100001];

bool sorti(concert a, concert b){
    return a.y<b.y;
}
int main()
{
   FILE *fin=fopen("heavymetal.in", "r");
   FILE *fout=fopen("heavymetal.out", "w");
   fscanf(fin,"%d", &n);
   for(i=1; i<=n; i++)
      fscanf(fin,"%d%d", &v[i].x, &v[i].y);
   sort(v+1, v+n+1, sorti);
   for(i=1; i<=n; i++){
        int l1=1, l2=i-1, o=0;
        while(l1<=l2){
            int mid=(l1+l2)/2;
            if(v[mid].y<=v[i].x){
                o=mid;
                l1=mid+1;
            }
            else
                l2=mid-1;
        }
        v[i].val=max(v[i-1].val, v[i].y-v[i].x+v[o].val);
   }
   fprintf(fout,"%d\n", v[n].val);
   return 0;
}
//Muie tibi daca te uiti