Cod sursa(job #1722217)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 27 iunie 2016 16:45:57
Problema Magazin Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.04 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define MAXN 30010
#define INF 1000000000
using namespace std;
vector<int> v[MAXN];
int dp[MAXN][6],best[MAXN];
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
int main(){
    freopen("magazin.in","r",stdin);
    freopen("magazin.out","w",stdout);
    int p,n,m,d,i,j,a,b;
    scanf("%d%d%d%d",&p,&n,&m,&d);
    m++;
    for(i=1;i<=p;i++){
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
    }
    for(i=1;i<=n;i++){
        if(v[i].size()==0)
            continue;
        sort(v[i].begin(),v[i].end());
        best[i]=minimum(2*(m-v[i][0]),2*v[i][v[i].size()-1]);
        for(j=0;j<v[i].size()-1;j++)
            best[i]=minimum(best[i],2*(v[i][j]+m-v[i][j+1]));
    }
    if(v[1].size()>0)
        dp[1][0]=2*v[1][v[1].size()-1];
    dp[1][1]=2*m;
    dp[1][2]=best[1];
    dp[1][3]=m;
    dp[1][4]=m;
    dp[1][5]=INF;
    for(i=2;i<=n;i++){
        dp[i][0]=minimum(dp[i-1][0],dp[i-1][1])+d;
        if(v[i].size()>0)
            dp[i][0]+=2*v[i][v[i].size()-1];
        dp[i][1]=dp[i-1][0]+d+2*m;
        dp[i][1]=minimum(dp[i][1],dp[i-1][1]+3*d+best[i]);
        dp[i][1]=minimum(dp[i][1],dp[i-1][2]+3*d+2*m);
        dp[i][1]=minimum(dp[i][1],dp[i-1][5]+3*d+m);
        dp[i][1]=minimum(dp[i][1],dp[i-1][3]+d+m);
        dp[i][2]=dp[i-1][0]+d+best[i];
        dp[i][2]=minimum(dp[i][2],dp[i-1][2]+3*d+best[i]);
        dp[i][3]=minimum(dp[i-1][3],dp[i-1][4])+d;
        if(v[i].size()>0)
            dp[i][3]+=2*(m-v[i][0]);
        dp[i][4]=dp[i-1][3]+d+2*m;
        dp[i][4]=minimum(dp[i][4],dp[i-1][4]+3*d+best[i]);
        dp[i][4]=minimum(dp[i][4],dp[i-1][5]+3*d+2*m);
        dp[i][4]=minimum(dp[i][4],dp[i-1][2]+3*d+m);
        dp[i][4]=minimum(dp[i][4],dp[i-1][0]+d+m);
        dp[i][5]=dp[i-1][3]+d+best[i];
        dp[i][5]=minimum(dp[i][5],dp[i-1][5]+3*d+best[i]);
        dp[i][0]=minimum(dp[i][0],dp[i][1]);
        dp[i][3]=minimum(dp[i][3],dp[i][4]);
    }
    printf("%d",minimum(dp[n][0],dp[n][1]));
    return 0;
}