Cod sursa(job #1778572)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 13 octombrie 2016 21:48:38
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 10005
using namespace std;
    
FILE *IN,*OUT;
int N,D[MaxN],P[MaxN];
struct _Interval
{
	int x,y;
}v[MaxN];
bool cond(int a,int b)
{
	return v[a].y<v[b].y||(v[a].y==v[b].y&&v[a].x<v[b].x);
}
int Binary_Search(int val)
{
	int hi=N,lw=1,mid,last=0;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(v[P[mid]].y<=val)
			last=mid,lw=mid+1;
		else hi=mid-1;
	}
	return last;
}
int main()
{
	IN=fopen("heavymetal.in","r");
	OUT=fopen("heavymetal.out","w");
	
	fscanf(IN,"%d",&N);
	for(int i=1;i<=N;i++)
	{
		fscanf(IN,"%d%d",&v[i].x,&v[i].y);
		P[i]=i;
	}
	sort(P+1,P+1+N,cond);
	for(int i=1;i<=N;i++)
		D[i]=max(D[i-1],D[Binary_Search(v[P[i]].x)]+v[P[i]].y-v[P[i]].x);
	fprintf(OUT,"%d",D[N]);
	return 0;
}