Cod sursa(job #2391003)

Utilizator Bodo171Bogdan Pop Bodo171 Data 28 martie 2019 16:40:09
Problema Magazin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=30005;
vector<int> v[nmax];
int cost[2][2];
int dp[nmax][2][3];
int P,n,m,d,i,j,k,x,y,ans;
void prp(int &a,int b)
{
    a=min(a,b);
}
int main()
{
    ifstream f("magazin.in");
    ofstream g("magazin.out");
    f>>P>>n>>m>>d;
    for(i=1;i<=P;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
    }
    for(i=0;i<2;i++)
        for(j=0;j<3;j++)
        dp[0][i][j]=(1<<30);
    dp[0][0][0]=-d;
    for(i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end());
        if(v[i].empty())
        {
            for(j=0;j<2;j++)
                for(k=0;k<2;k++)
                  cost[j][k]=0;
        }
        else
        {
            cost[0][0]=2*v[i].back();
            cost[1][0]=2*(m+1-v[i].front());
            cost[0][1]=cost[1][1]=min(cost[0][0],cost[1][0]);
            for(j=0;j+1<v[i].size();j++)
                cost[0][1]=min(cost[0][1],2*v[i][j]+2*(m+1-v[i][j+1]));
             for(j=0;j+1<v[i].size();j++)
                cost[1][1]=min(cost[1][1],2*v[i][j]+2*(m+1-v[i][j+1]));
        }
        for(j=0;j<2;j++)
            for(k=0;k<3;k++)
              dp[i][j][k]=(1<<30);
        //0-normal
        //1-a fost inchis
        //2-trebuie inchis
        for(j=0;j<2;j++)
        {
            prp(dp[i][j][0],dp[i-1][j][0]+d+cost[j][0]);
            prp(dp[i][j][0],dp[i-1][(1-j)][0]+d+m+1);
            prp(dp[i][j][0],dp[i-1][(1-j)][2]+3*d+m+1);
            prp(dp[i][j][0],dp[i-1][j][2]+3*d+2*(m+1));
            prp(dp[i][j][0],dp[i-1][j][1]+d+cost[j][0]);

            prp(dp[i][j][1],dp[i-1][j][1]+3*d+cost[j][1]);
            prp(dp[i][j][1],dp[i-1][j][0]+2*(m+1)+d);
            prp(dp[i][j][1],dp[i-1][j][2]+2*(m+1)+3*d);
            prp(dp[i][j][1],dp[i-1][(1-j)][0]+(m+1)+d);
            prp(dp[i][j][1],dp[i-1][(1-j)][2]+(m+1)+3*d);

            prp(dp[i][j][2],dp[i-1][j][0]+d+cost[j][1]);
            prp(dp[i][j][2],dp[i-1][j][1]+d+cost[j][1]);
            prp(dp[i][j][2],dp[i-1][j][2]+3*d+cost[j][1]);

            dp[i][j][0]=min(dp[i][j][0],dp[i][j][1]);
        }
    }
    ans=min(dp[n][0][0],dp[n][0][1]);
    g<<ans;
    return 0;
}