Pagini recente » Cod sursa (job #3254271) | Cod sursa (job #1607689) | Cod sursa (job #2393706) | Cod sursa (job #3291877) | Cod sursa (job #2779760)
#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;
}