Cod sursa(job #1053329)

Utilizator darrenRares Buhai darren Data 12 decembrie 2013 17:53:25
Problema Magazin Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.52 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int P, N, M, D;
int minD[30002][6], best[30002];
vector<int> V[30002];

/*

0 - front jos, singur
1 - front jos, sus, conectat
2 - front jos, sus, se va conecta
3 - front sus, singur
4 - front sus, jos, conectat
5 - front sus, jos, se va conecta

*/

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

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

    for (int i = 1, xn, yn; i <= P; ++i)
    {
        fin >> xn >> yn;
        V[xn].push_back(yn);
    }
    for (int i = 1; i <= N; ++i)
    {
        if (V[i].empty()) continue;
        sort(V[i].begin(), V[i].end());

        best[i] = 2 * (M - V[i].front());
        for (int j = 0; j < int(V[i].size()) - 1; ++j)
            best[i] = min(best[i], 2 * (V[i][j] + M - V[i][j + 1]));
        best[i] = min(best[i], 2 * V[i].back());
    }

    if (!V[1].empty()) minD[1][0] += 2 * V[1].back();
    minD[1][1] = 2 * M;
    minD[1][2] = best[1];
    minD[1][3] = M;
    minD[1][4] = M;
    minD[1][5] = 0x3f3f3f3f;

    for (int i = 2; i <= N; ++i)
    {
        minD[i][0] = min(minD[i - 1][0], minD[i - 1][1]) + D;
        if (!V[i].empty()) minD[i][0] += 2 * V[i].back();

        minD[i][1] = minD[i - 1][0] + D + 2 * M;
        minD[i][1] = min(minD[i][1], minD[i - 1][1] + 3 * D + best[i]);
        minD[i][1] = min(minD[i][1], minD[i - 1][2] + 3 * D + 2 * M);
        minD[i][1] = min(minD[i][1], minD[i - 1][5] + 3 * D + M);
        minD[i][1] = min(minD[i][1], minD[i - 1][3] + D + M);

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

        minD[i][3] = min(minD[i - 1][3], minD[i - 1][4]) + D;
        if (!V[i].empty()) minD[i][3] += 2 * (M - V[i].front());

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

        minD[i][5] = minD[i - 1][3] + D + best[i];
        minD[i][5] = min(minD[i][5], minD[i - 1][5] + 3 * D + best[i]);

        minD[i][0] = min(minD[i][0], minD[i][1]);
        minD[i][3] = min(minD[i][3], minD[i][4]);
    }

    fout << min(minD[N][0], minD[N][1]) << '\n'; // trebuie sa fie deja unite

    fin.close();
    fout.close();
}