Cod sursa(job #2636269)

Utilizator giotoPopescu Ioan gioto Data 17 iulie 2020 13:56:15
Problema Magazin Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.65 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));
    ++m;

    dp[0][0][0] = 0;
    dp[0][1][0] = m;

    for (int i = 1; i <= n ; ++i) {
        if (!v[i].empty()) {
            sort(v[i].begin(), v[i].end());

            st[i] = v[i][0];
            dr[i] = v[i].back();
        }
        else st[i] = m, dr[i] = 0;

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

        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]));

        ///ignor culoarul sau o parte din culoar
        int idealDist = min(2 * dr[i], 2 * (m - st[i]));
        for (int j = 0; j + 1 < v[i].size() ; ++j)
            idealDist = min(idealDist, 2 * (m - v[i][j + 1]) + 2 * v[i][j]);

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

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

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

        ///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], min(dp[i][1][1], dp[i][0][2]) + m);
        dp[i][1][0] = min(dp[i][1][0], min(dp[i][0][1], dp[i][1][2]) + 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]);

        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);
    }

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

    return 0;
}