Cod sursa(job #470645)

Utilizator hendrikHendrik Lai hendrik Data 15 iulie 2010 07:30:12
Problema Magazin Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(int)(a);i<=(int)(b);i++)
#define N 50010
#define M 30010
#define pb push_back
#define sz size()
const int oo=(int)1e9;
int p,n,m,d,a,b,c,f[N][6];
vector<int>g[M];

void open(){
	freopen("magazin.in","r",stdin);
	freopen("magazin.out","w",stdout);
}

int main(){
	open();
	scanf("%d%d%d%d",&p,&n,&m,&d);
	REP(i,p){
		scanf("%d%d",&a,&b);
		g[a].pb(b);
	}
	REP(i,6){
		f[0][i]=oo;
	}
	f[0][2]=0;
	FOR(i,1,n){
		if (g[i].sz==0){
			a=b=c=0;
		}
		else {
			sort(g[i].begin(),g[i].end());
			a=m+1-g[i][0];
			b=g[i][g[i].sz-1];
			c=min(a,b);
			REP(j,g[i].sz-2){
				c=min(c,m+1+g[i][j]-g[i][j+1]);
			}
			a<<=1;b<<=1;c<<=1;
		}
		//0
		f[i][0]=f[i-1][0]+a+d;
		f[i][0]=min(f[i][0],f[i-1][1]+m+1+d);
		f[i][0]=min(f[i][0],f[i-1][2]+m+1+d);
		f[i][0]=min(f[i][0],f[i-1][3]+c+d);
		f[i][0]=min(f[i][0],f[i-1][4]+m+1+d);
		f[i][0]=min(f[i][0],f[i-1][5]+2*(m+1)+d);
		
		//1
		f[i][1]=f[i-1][0]+m+1+3*d;
		f[i][1]=min(f[i][1],f[i-1][1]+c+3*d);
		f[i][1]=min(f[i][1],f[i-1][2]+2*(m+1)+3*d);
		f[i][1]=min(f[i][1],f[i-1][3]+m+1+3*d);
		f[i][1]=min(f[i][1],f[i-1][4]+2*(m+1)+3*d);
		f[i][1]=min(f[i][1],f[i-1][5]+m+1+3*d);
		
		//2
		f[i][2]=f[i-1][0]+m+1+d;
		f[i][2]=min(f[i][2],f[i-1][1]+c+d);
		f[i][2]=min(f[i][2],f[i-1][2]+b+d);
		f[i][2]=min(f[i][2],f[i-1][3]+m+1+d);
		f[i][2]=min(f[i][2],f[i-1][4]+2*(m+1)+d);
		f[i][2]=min(f[i][2],f[i-1][5]+m+1+d);
		
		//3
		f[i][3]=f[i-1][0]+2*(m+1)+3*d;
		f[i][3]=min(f[i][3],f[i-1][1]+m+1+3*d);
		f[i][3]=min(f[i][3],f[i-1][2]+m+1+3*d);
		f[i][3]=min(f[i][3],f[i-1][3]+c+3*d);
		f[i][3]=min(f[i][3],f[i-1][4]+m+1+3*d);
		f[i][3]=min(f[i][3],f[i-1][5]+2*(m+1)+3*d);
		
		//4
		f[i][4]=f[i-1][0]+m+1+d;
		f[i][4]=min(f[i][4],f[i-1][1]+c+d);
		f[i][4]=min(f[i][4],f[i-1][2]+b+d);
		f[i][4]=min(f[i][4],f[i-1][3]+m+1+d);
		f[i][4]=min(f[i][4],f[i-1][4]+c+3*d);
		f[i][4]=min(f[i][4],f[i-1][5]+m+1+d);
		
		//5
		f[i][5]=f[i-1][0]+a+d;
		f[i][5]=min(f[i][5],f[i-1][1]+m+1+d);
		f[i][5]=min(f[i][5],f[i-1][2]+m+1+d);
		f[i][5]=min(f[i][5],f[i-1][3]+c+d);
		f[i][5]=min(f[i][5],f[i-1][4]+m+1+d);
		f[i][5]=min(f[i][5],f[i-1][5]+c+3*d);
	}
	printf("%d\n",min(f[n][2]-d,f[n][1]-3*d));
	//system("pause");
	return 0;
}