Cod sursa(job #2334213)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 2 februarie 2019 12:38:49
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int d[N];
struct roaceri{
  int s,t;
};
bool cmp (roaceri a,roaceri b){
  if(a.t<b.t)
    return true;
  if(a.t==b.t)
    if(a.s<b.s)
      return true;
  return false;
}
roaceri v[N];
int n;
int cautb(int val){
  int pas=0,p2=1<<20;
  while(p2){
    if(pas+p2<=n && v[pas+p2].t<=val)
      pas+=p2;
    p2/=2;
  }
  return pas;
}
int  main()
{
    FILE*fin,*fout;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    int i;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++){
      fscanf(fin,"%d%d",&v[i].s,&v[i].t);
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
      int poz=cautb(v[i].s);
      d[i]=max(d[i-1],d[poz]+v[i].t-v[i].s);
    }
    fprintf(fout,"%d",d[n]);
    return 0;
}