Cod sursa(job #2636212)

Utilizator giotoPopescu Ioan gioto Data 17 iulie 2020 11:42:37
Problema Magazin Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 3e4 + 5;
const int INF = 1e9;

int p, n, m, d;
int st[DIM], dr[DIM];
int dp[DIM][2][3];
vector <int> v[DIM];

int main()
{
    freopen("magazin.in", "r", stdin);
    freopen("magazin.out", "w", stdout);

    scanf("%d%d%d%d", &p, &n, &m, &d);

    int x, y;
    for (int i = 1; i <= p ; ++i) {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;

    ++m;
    for (int i = 1; i <= n ; ++i) {
        if (v[i].empty()) {
            for (int j = 0; j <= 1 ; ++j)
                for (int k = 0; k <= 2 ; ++k)
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + d + 2 * d * (k != 0));

            ///incerc sa inchid starile de 1 si 2
            dp[i][0][0] = min(dp[i][0][0], dp[i - 1][1][1] + m + 3 * d);
            dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + m + 3 * d);

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

            ///incerc sa schimb partea
            dp[i][0][0] = min(dp[i][0][0], dp[i][1][0] + m);
            dp[i][1][0] = min(dp[i][1][0], dp[i][0][0] + m);

            dp[i][0][0] = min(dp[i][0][0], dp[i][1][2]);
            dp[i][1][0] = min(dp[i][1][0], dp[i][0][2]);
            continue ;
        }

        sort(v[i].begin(), v[i].end());

        for (int j = 0; j < v[i].size() ; ++j) ++v[i][j];

        st[i] = v[i][0];
        dr[i] = v[i].back();

        ///tranzitiile normale
        dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0] + d + 2 * dr[i]);
        dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][0] + d + 2 * (m - st[i] + 1));

        for (int k = 1; k <= 2 ; ++k) {
            dp[i][0][k] = min(dp[i][0][k], dp[i - 1][0][k] + 3 * d + 2 * dr[i]);
            dp[i][1][k] = min(dp[i][1][k], dp[i - 1][1][k] + 3 * d + 2 * (m - st[i] + 1));
        }

        ///ignor culoarul sau o parte din culoar
        dp[i][0][1] = min(dp[i][0][1], min(dp[i - 1][0][0], dp[i - 1][0][1] + 2 * d) + d + 2 * (m - st[i] + 1));
        dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][1][0], dp[i - 1][1][1] + 2 * d) + d + 2 * dr[i]);

        dp[i][0][2] = min(dp[i][0][2], min(dp[i - 1][0][0] + m, dp[i - 1][0][2] + 2 * d + 2 * (m - st[i] + 1)) + d);
        dp[i][1][2] = min(dp[i][1][2], min(dp[i - 1][1][0] + m, dp[i - 1][1][2] + 2 * d + 2 * dr[i]) + d);

        for (int j = 0; j + 1 < v[i].size() ; ++j) {
            dp[i][0][1] = min(dp[i][0][1], min(dp[i - 1][0][0], dp[i - 1][0][1] + 2 * d) + d + 2 * (m - v[i][j + 1] + 1) + 2 * v[i][j]);
            dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][0][0], dp[i - 1][0][1] + 2 * d) + d + 2 * (m - v[i][j + 1] + 1) + 2 * v[i][j]);

            dp[i][0][2] = min(dp[i][0][2], dp[i - 1][0][2] + 3 * d + 2 * (m - v[i][j + 1] + 1) + 2 * v[i][j]);
            dp[i][1][2] = min(dp[i][1][2], dp[i - 1][1][2] + 3 * d + 2 * (m - v[i][j + 1] + 1) + 2 * v[i][j]);
        }

        ///incerc sa inchid starile de 1 si 2
        dp[i][0][0] = min(dp[i][0][0], dp[i - 1][1][1] + m + 3 * d);
        dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + m + 3 * d);

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

        ///incerc sa schimb partea
        dp[i][0][0] = min(dp[i][0][0], dp[i][1][0] + m);
        dp[i][1][0] = min(dp[i][1][0], dp[i][0][0] + m);

        dp[i][0][0] = min(dp[i][0][0], dp[i][1][2]);
        dp[i][1][0] = min(dp[i][1][0], dp[i][0][2]);
    }

    printf("%d", dp[n][0][0] - d);

    return 0;
}