Cod sursa(job #2734081)

Utilizator dimi999Dimitriu Andrei dimi999 Data 31 martie 2021 12:54:56
Problema Magazin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <bits/stdc++.h>
#define MAX 100000000
using namespace std;

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

int dp[6][30005];
///1-incep de sus ajung sus
///0-incep de jos ajung jos
///3-incep de sus, ajung jos prin culoar ulterior
///2-.........jos.......sus
///5-sus->jos prin culoar anterior
///4-jos->sus
int aux[3];

vector <int> v[30005];

int main()
{
    int N, M, D, P;

    fin >> P >> N >> M >> D;

    M++;

    for(int i = 1; i <= P; i++)
    {
        int x, y;

        fin >> x >> y;

        v[x].push_back(y);
    }

    for(int i = 1; i <= N; i++)
    {
        sort(v[i].begin(), v[i].end());

        fill(aux + 0, aux + 3, 0);

        if(v[i].size() > 0)
        {
            aux[0] = 2 * v[i][v[i].size() - 1];
            aux[1] = 2 * (M - v[i][0]);
        }

        aux[2] = min(aux[1], aux[0]);

        for(int j = 1; j < v[i].size(); j++)
            aux[2] = min(aux[2], 2 * (v[i][j - 1] + M - v[i][j]));

        if(i == 1)
        {
            dp[0][1] = aux[0];
            dp[1][1] = MAX;

            dp[2][1] = aux[2];
            dp[3][1] = dp[5][1] = MAX;

            dp[4][1] = M;
            continue;
        }

        dp[0][i] = min(aux[0] + dp[0][i - 1] + D, aux[0] + dp[5][i - 1] + D);
        dp[1][i] = min(aux[1] + dp[1][i - 1] + D, aux[1] + dp[4][i - 1] + D);

        dp[2][i] = min(aux[2] + dp[0][i - 1] + D, aux[2] + 3 * D + dp[2][i - 1]);
        dp[3][i] = min(aux[2] + dp[1][i - 1] + D, aux[2] + 3 * D + dp[3][i - 1]);

        dp[4][i] = min(min(dp[0][i - 1] + M + D, dp[2][i - 1] + D * 3 + M),
                       min(dp[4][i - 1] + D * 3 + aux[2], dp[5][i - 1] + D + M));
        dp[5][i] = min(min(dp[1][i - 1] + M + D, dp[3][i - 1] + D * 3 + M),
                       min(dp[5][i - 1] + D * 3 + aux[2], dp[4][i - 1] + D + M));

        dp[0][i] = min(MAX, dp[0][i]);
        dp[1][i] = min(MAX, dp[1][i]);
        dp[2][i] = min(MAX, dp[2][i]);
        dp[3][i] = min(MAX, dp[3][i]);
        dp[4][i] = min(MAX, dp[4][i]);
        dp[5][i] = min(MAX, dp[5][i]);
    }

    fout << min(dp[0][N], dp[5][N]);

    return 0;
}