Cod sursa(job #2014752)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 24 august 2017 12:53:23
Problema Magazin Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("magazin.in");
ofstream g("magazin.out");
int p,n,m,d,i,x,y,j,dp[1<<15][2][3],a[1<<15],b[1<<15][2];
vector<int> V[1<<15];
int main()
{
    f>>p>>n>>m>>d;
    ++m;
    for(i=1;i<=p;++i)
    {
        f>>x>>y;
        V[x].push_back(y);
    }
    for(i=1;i<=n;++i)
    if(V[i].size())
    {
        sort(V[i].begin(),V[i].end());
        b[i][0]=2*V[i].back();
        b[i][1]=2*(m-V[i][0]);
        a[i]=min(b[i][0],b[i][1]);
        for(j=0;j<V[i].size()-1;++j)
            a[i]=min(a[i],2*(V[i][j]+m-V[i][j+1]));
    }
    dp[1][0][0]=b[1][0];
    dp[1][0][1]=a[1];
    dp[1][0][2]=2*m;
    dp[1][1][0]=dp[1][1][1]=1<<30;
    dp[1][1][2]=m;
    for(i=2;i<=n;++i)
        for(j=0;j<2;++j)
        {
            dp[i][j][0]=d+b[i][j]+min(dp[i-1][j][0],dp[i-1][j][2]);
            dp[i][j][1]=a[i]+min(min(dp[i-1][j][0]+d,dp[i-1][j][1]+3*d),dp[i-1][j][2]+d);
            dp[i][j][2]=min(min(dp[i][j][1]-a[i]+2*m,dp[i-1][j][2]+a[i]+3*d),min(min(dp[i-1][1^j][0]+d,dp[i-1][1^j][1]+3*d),dp[i-1][1^j][2]+d)+m);
        }
    g<<min(dp[n][0][0],dp[n][0][2]);
    return 0;
}