Pagini recente » Cod sursa (job #1835901) | Cod sursa (job #14851) | Cod sursa (job #1758923) | Cod sursa (job #678996) | Cod sursa (job #1742219)
#include <bits/stdc++.h>
#define maxN 30002
#define maxM 27
#define pb push_back
#define inf 1000000000
using namespace std;
int p, n, m, d, ans, dp[maxN][2][3], a[maxN], b[maxN][2];
vector < int > V[maxN];
int Min(int x, int y)
{
return x < y ? x : y;
}
void read()
{
int i;
freopen("magazin.in", "r", stdin);
scanf("%d %d %d %d", &p, &n, &m, &d);
for (i = 1; i <= p; ++ i)
{
int x, y;
scanf("%d %d", &x, &y);
V[x].pb(y);
}
}
void solve()
{
int i, j;
for (i = 1; i <= n; ++ i)
if (V[i].size())
{
sort(V[i].begin(), V[i].end());
a[i] = Min(2 * V[i].back(), 2 * (m - V[i].front()));
b[i][0] = 2 * V[i].back();
b[i][1] = 2 * (m - V[i].front());
for (j = 0; j < V[i].size() - 1; ++ j)
a[i] = Min(a[i], 2 * (V[i][j] + m - V[i][j + 1]));
}
dp[1][0][0] = b[1][0];
dp[1][0][1] = a[1];
dp[1][0][2] = 2 * m;
dp[1][1][0] = inf;
dp[1][1][1] = inf;
dp[1][1][2] = m;
for (i = 2; i <= n; ++ i)
for (j = 0; j < 2; ++ j)
{
dp[i][j][0] = Min(d + b[i][j] + dp[i - 1][j][0],
d + b[i][j] + dp[i - 1][j][2]);
dp[i][j][1] = Min(dp[i - 1][j][0] + d + a[i], Min(dp[i - 1][j][1] + 3 * d + a[i], dp[i - 1][j][2] + d + a[i]));
dp[i][j][2] = Min(Min(Min(Min(dp[i - 1][j][0] + d + 2 * m, dp[i - 1][j][1] + 3 * d + 2 * m), dp[i - 1][j][2] + d + 2 * m),
dp[i - 1][j][2] + a[i] + 3 * d),
Min(Min(dp[i - 1][1 - j][0] + d + m, dp[i - 1][1 - j][1] + 3 * d + m), dp[i - 1][1 - j][2] + d + m));
}
ans = Min(dp[n][0][0] + d, dp[n][0][2] + 2 * d);
}
void write()
{
freopen("magazin.out", "w", stdout);
printf("%d\n", ans);
}
int main()
{
read();
solve();
write();
return 0;
}