Cod sursa(job #961351)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 11 iunie 2013 22:04:16
Problema Wanted Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
#include<algorithm>

#define maxn 205

using namespace std;

FILE*f=fopen("wanted.in","r");
FILE*g=fopen("wanted.out","w");

const int inf = (1LL<<31)-1;
int n;
int D[maxn][maxn][2];
pair<int,int>P[maxn];

inline int modul ( const int &j ){
	if ( j < 0 )	return -j;
	return j;
}

inline int solve ( int st , int dr , int side ){
	if ( D[st][dr][side] )	return D[st][dr][side];
	if ( st == dr )	return P[st].second;
	
	int startx = P[st].first;
	if ( side == 1 )	startx = P[dr].first;
	
	D[st][dr][side] = inf;
	for ( int i = st ; i <= dr ; ++i ){
		int left = 0,right = 0;
		
		if ( i > st ){
			left = solve(st,i-1,1) + P[i].first-P[i-1].first;
		}
		if ( i < dr ){
			right = solve(i+1,dr,0) + P[i+1].first-P[i].first;
		}
		
		D[st][dr][side] = min(D[st][dr][side],max(left,right)+modul(startx-P[i].first)+(P[i].second<<1));
	}
	
	return D[st][dr][side];
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&P[i].first,&P[i].second);
	}
	
	sort(P+1,P+n+1);
	
	int sol = inf;
	for ( int i = 1 ; i <= n ; ++i ){
		int left = 0,right = 0;
		if ( i > 1 ){
			left = solve(1,i-1,1) + P[i].first-P[i-1].first;
		}
		if ( i < n ){
			right = solve(i+1,n,0) + P[i+1].first-P[i].first;
		}
		
		sol = min(sol,max(left,right)+modul(P[i].first)+(P[i].second<<1));
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}