Cod sursa(job #1312562)

Utilizator BlackBird_v.1.0Stephen Berg BlackBird_v.1.0 Data 9 ianuarie 2015 18:26:36
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
#define l64 long long 
#define final second
#define start first
#define Nmax 100013
int i,j,n,a,b;
vector < pair < int,int > > V;
l64 d[Nmax];

bool comp (pair <int, int> a, pair <int,int> b)
{
 return (a.final<b.final || (a.final==b.final && a.start<b.start));
}

l64 search(int left, int right,l64 start)
 {
  int middle,ans;
  while(left<=right)
      {
       middle=(left+right)/2;
       if (V[middle].final<=start) left=middle+1;			
             else right=middle-1; 
      }
  return right;
 }

int main(void)
{
 ifstream cin("heavymetal.in");
 ofstream cout("heavymetal.out");
 cin>>n;
  for (i=1;i<=n;++i) 
   {
   	cin>>a>>b;
   	V.push_back(make_pair(a,b));
   }
 sort(V.begin(),V.end(),comp);
 d[0]=V[0].final-V[0].start;
 for (i=1;i<n;++i)
   d[i]=max(d[i-1],V[i].final-V[i].start+d[search(0,i-1,V[i].start)]);
 cout<<1LL*d[n-1]<<"\n";
 return 0;
}