Cod sursa(job #2779760)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 4 octombrie 2021 21:01:21
Problema Magazin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX(30005), INF(1 << 30);
int dp[6][NMAX];
/*dp[0][i] = costul minim ca drumul sa treaca prin coltul sus a lui i, fara sa treaca prin cel de jos
  dp[1][i] = costul minim ca drumul sa treaca prin coltul de sus a lui i, si prin coltul de jos a lui i, da cele doua trasee se unesc
  dp[2][i] = costul minim ca drumul sa treaca prin coltul de sus a lui i, si prin coltul de jos a lui i, da fara sa se uneasca cele doua trasee ( > i)
  dp[3][i] = costul minim ca drumul sa treaca prin coltul jos a lui i, fara sa treaca prin cel de sus
  dp[4][i] = costul minim ca drumul sa treaca prin coltul de jos a lui i, si prin coltul de sus a lui i, da cele doua trasee se unesc
  dp[5][i] = costul minim ca drumul sa treaca prin coltul de jos a lui i, si prin coltul de sus a lui i, da fara sa se uneasca cele doua trasee ( > i)
*/
vector<int> v[NMAX];
int main()
{
    int p, n, m, d;
    fin >> p >> n >> m >> d;
    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)
    {
        int distDeSusJos = 0, distJosSus = 0, mini = 0;
        if(v[i].size())
        {
            sort(v[i].begin(), v[i].end());
            distDeSusJos = m - v[i][0] + 1;
            distJosSus = v[i][v[i].size() - 1];
            mini = min(distDeSusJos, distJosSus);
            for(int j = 0; j < (int)v[i].size() - 1; ++j)
                mini = min(mini, v[i][j] + m + 1 - v[i][j + 1]);
            distDeSusJos *= 2;
            distJosSus *= 2;
            mini *= 2;
        }
        dp[0][i] = dp[1][i] = dp[2][i] = dp[3][i] = dp[4][i] = dp[5][i] = INF;
        if(i == 1)
        {
            dp[3][i] = distJosSus;
            dp[4][i] = m + 1;
            dp[5][i] = mini;
        }
        else
        {
            dp[0][i] = min(dp[0][i], min(dp[0][i - 1] + d + distDeSusJos, dp[4][i - 1] + d + distDeSusJos));

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

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

            dp[3][i] = min(dp[3][i], min(dp[1][i - 1] + distJosSus + d, dp[3][i - 1] + distJosSus + d));

            dp[4][i] = min(dp[4][i], min(dp[1][i - 1] + d + m + 1, min(dp[3][i - 1] + d + m + 1, min(dp[4][i - 1] + 3 * d + mini, dp[5][i - 1] + 3 * d + m + 1))));

            dp[5][i] = min(dp[5][i], min(dp[3][i - 1] + d + mini, dp[5][i - 1] + 3 * d + mini));
        }
    }
    fout << min(dp[1][n], dp[3][n]) << '\n';
    return 0;
}