Cod sursa(job #2879400)

Utilizator puica2018Puica Andrei puica2018 Data 28 martie 2022 15:35:39
Problema Magazin Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("magazin.in");
ofstream fout("magazin.out");

int p,n,m,d;
int bnt[30005],best[2][30005],dp[30005][2][3];
vector <int> v[30005];

int main()
{
    fin>>p>>n>>m>>d;
    for(int i=1; i<=p; i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
    }
    m++;
    for(int i=1; i<=n; i++)
    {
        if(v[i].empty())
            continue;
        sort(v[i].begin(),v[i].end());
        bnt[i]=min(2*v[i].back(),2*(m-v[i].front()));
        for(int j=0; j<v[i].size()-1; j++)
            bnt[i]=min(bnt[i],2*(m-v[i][j+1]+v[i][j]));
        best[0][i]=2*v[i].back();
        best[1][i]=2*(m-v[i].front());
    }
    dp[1][0][0]=best[0][1];
    dp[1][0][1]=bnt[1];
    dp[1][0][2]=2*m;
    dp[1][1][0]=1e9;
    dp[1][1][1]=1e9;
    dp[1][1][2]=m;
    for(int i=2; i<=n; i++)
    {
        for(int j=0; j<2; j++)
        {
            dp[i][j][0]=min(dp[i-1][j][0]+d+best[j][i],
                            dp[i-1][j][2]+d+best[j][i]);
            dp[i][j][1]=min({dp[i-1][j][0]+d+bnt[i],
                             dp[i-1][j][1]+3*d+bnt[i],
                             dp[i-1][j][2]+d+bnt[i]});
            dp[i][j][2]=min({dp[i-1][j][0]+d+2*m,
                             dp[i-1][j][1]+3*d+2*m,
                             dp[i-1][j][2]+3*d+bnt[i],
                             dp[i-1][j][2]+d+2*m,
                             dp[i-1][1-j][0]+d+m,
                             dp[i-1][1-j][1]+3*d+m,
                             dp[i-1][1-j][2]+d+m});
        }
    }
    fout<<min(dp[n][0][0],dp[n][0][2])<<"\n";
    return 0;
}