Cod sursa(job #1742219)

Utilizator akaprosAna Kapros akapros Data 15 august 2016 23:06:26
Problema Magazin Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define maxN 30002
#define maxM 27
#define pb push_back
#define inf 1000000000
using namespace std;
int p, n, m, d, ans, dp[maxN][2][3], a[maxN], b[maxN][2];
vector < int > V[maxN];
int Min(int x, int y)
{
    return x < y ? x : y;
}
void read()
{
    int i;
    freopen("magazin.in", "r", stdin);
    scanf("%d %d %d %d", &p, &n, &m, &d);
    for (i = 1; i <= p; ++ i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        V[x].pb(y);
    }
}
void solve()
{
    int i, j;
    for (i = 1; i <= n; ++ i)
        if (V[i].size())
        {
            sort(V[i].begin(), V[i].end());
            a[i] = Min(2 * V[i].back(), 2 * (m - V[i].front()));
            b[i][0] = 2 * V[i].back();
            b[i][1] = 2 * (m - V[i].front());
            for (j = 0; j < V[i].size() - 1; ++ j)
                a[i] = Min(a[i], 2 * (V[i][j] + m - V[i][j + 1]));
        }
    dp[1][0][0] = b[1][0];
    dp[1][0][1] = a[1];
    dp[1][0][2] = 2 * m;
    dp[1][1][0] = inf;
    dp[1][1][1] = inf;
    dp[1][1][2] = m;
    for (i = 2; i <= n; ++ i)
        for (j = 0; j < 2; ++ j)
        {
            dp[i][j][0] = Min(d + b[i][j] + dp[i - 1][j][0],
                                            d + b[i][j] + dp[i - 1][j][2]);

            dp[i][j][1] = Min(dp[i - 1][j][0] + d + a[i], Min(dp[i - 1][j][1] + 3 * d + a[i], dp[i - 1][j][2] + d + a[i]));

            dp[i][j][2] = Min(Min(Min(Min(dp[i - 1][j][0] + d + 2 * m, dp[i - 1][j][1] + 3 * d + 2 * m), dp[i - 1][j][2] + d + 2 * m),
                                  dp[i - 1][j][2] + a[i] + 3 * d),
                              Min(Min(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));

        }
    ans = Min(dp[n][0][0] + d, dp[n][0][2] + 2 * d);
}
void write()
{
    freopen("magazin.out", "w", stdout);
    printf("%d\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}