Cod sursa(job #2548393)

Utilizator stef2003Bud Stefan stef2003 Data 16 februarie 2020 16:40:44
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct ura{
  int in, sf;
};

ura v[100001];
int sol[100000];

bool cmp(ura a, ura b) {
  if(a.sf<b.sf)
    return true;
  return false;
}

int main() {
  FILE *fin, *fout;
  int n, i, j, dur, st, mij, dr, u;
  fin=fopen("heavymetal.in","r");
  fout=fopen("heavymetal.out","w");
  fscanf(fin, "%d",&n);
  for(i=1;i<=n;i++)
    fscanf(fin, "%d%d",&v[i].in,&v[i].sf);
  sort(v+1,v+n+1,cmp);
  sol[1]=v[1].sf-v[1].in;
  for(i=2;i<=n;i++) {
    sol[i]=sol[i-1];
    dur=v[i].sf-v[i].in;
    st=1;
    dr=i;
    u=-1;
    while(st<=dr) {
      mij=(st+dr)/2;
      if(v[mij].sf<=v[i].in) {
        st=mij+1;
        u=mij;
      }
      else
        dr=mij-1;
    }
    if(sol[u]+dur>sol[i])
      sol[i]=sol[u]+dur;
  }
  fprintf(fout, "%d",sol[n]);
  fclose( fin );
  fclose( fout );
  return 0;
}