Pagini recente » Cod sursa (job #2236334) | Cod sursa (job #1704712) | Cod sursa (job #1777869) | Cod sursa (job #546970) | Cod sursa (job #1053321)
#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][0]);
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] = 0x3f3f3f3f;
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][2] + 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]);
}
printf("%d\n", minD[3][4]);
fout << min(minD[N][0], minD[N][1]) << '\n'; // trebuie sa fie deja unite
fin.close();
fout.close();
}