Pagini recente » Cod sursa (job #3262077) | Cod sursa (job #3268252) | Cod sursa (job #2608171) | Cod sursa (job #3273915) | Cod sursa (job #2636245)
#include <bits/stdc++.h>
using namespace std;
const int DIM = 3e4 + 5;
const int INF = 1e9;
int p, n, m, d;
int st[DIM], dr[DIM];
int dp[DIM][2][3];
vector <int> v[DIM];
int main()
{
freopen("magazin.in", "r", stdin);
freopen("magazin.out", "w", stdout);
scanf("%d%d%d%d", &p, &n, &m, &d);
int x, y;
for (int i = 1; i <= p ; ++i) {
scanf("%d%d", &x, &y);
v[x].push_back(y);
}
memset(dp, 0x3f, sizeof(dp));
++m;
dp[0][0][0] = 0;
dp[0][1][0] = m;
for (int i = 1; i <= n ; ++i) {
if (!v[i].empty()) {
sort(v[i].begin(), v[i].end());
st[i] = v[i][0];
dr[i] = v[i].back();
}
else st[i] = m, dr[i] = 0;
///tranzitiile normale
dp[i][0][0] = min(dp[i][0][0], dp[i - 1][1][0] + d + m);
dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][0] + d + m);
dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0] + d + 2 * dr[i]);
dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][0] + d + 2 * (m - st[i]));
for (int k = 1; k <= 2 ; ++k) {
dp[i][0][k] = min(dp[i][0][k], dp[i - 1][0][k] + 3 * d + 2 * dr[i]);
dp[i][1][k] = min(dp[i][1][k], dp[i - 1][1][k] + 3 * d + 2 * (m - st[i]));
}
///ignor culoarul sau o parte din culoar
int idealDist = min(2 * dr[i], 2 * (m - st[i]));
for (int j = 0; j + 1 < v[i].size() ; ++j)
idealDist = min(idealDist, 2 * (m - v[i][j + 1]) + 2 * v[i][j]);
dp[i][0][1] = min(dp[i][0][1], min(dp[i - 1][0][0], dp[i - 1][0][1] + 2 * d) + d + idealDist);
dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][1][0], dp[i - 1][1][1] + 2 * d) + d + idealDist);
dp[i][0][2] = min(dp[i][0][2], min(dp[i - 1][0][0] + m, dp[i - 1][0][2] + 2 * d + idealDist) + d);
dp[i][1][2] = min(dp[i][1][2], min(dp[i - 1][1][0] + m, dp[i - 1][1][2] + 2 * d + idealDist) + d);
///incerc sa inchid starile de 1 si 2
dp[i][0][0] = min(dp[i][0][0], dp[i - 1][1][1] + m + 3 * d);
dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + m + 3 * d);
dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][2] + m + 3 * d);
dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][2] + m + 3 * d);
///incerc sa schimb partea
dp[i][0][0] = min(dp[i][0][0], dp[i][1][2]);
dp[i][1][0] = min(dp[i][1][0], dp[i][0][2]);
dp[i][0][0] = min(dp[i][0][0], dp[i][1][0] + m);
dp[i][1][0] = min(dp[i][1][0], dp[i][0][0] + m);
}
printf("%d", dp[n][0][0] - d);
return 0;
}