Pagini recente » Cod sursa (job #959603) | Cod sursa (job #1084715) | Clasament fmi-no-stress-10 | Cod sursa (job #2973829) | Cod sursa (job #2734081)
#include <bits/stdc++.h>
#define MAX 100000000
using namespace std;
ifstream fin("magazin.in");
ofstream fout("magazin.out");
int dp[6][30005];
///1-incep de sus ajung sus
///0-incep de jos ajung jos
///3-incep de sus, ajung jos prin culoar ulterior
///2-.........jos.......sus
///5-sus->jos prin culoar anterior
///4-jos->sus
int aux[3];
vector <int> v[30005];
int main()
{
int N, M, D, P;
fin >> P >> N >> M >> D;
M++;
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++)
{
sort(v[i].begin(), v[i].end());
fill(aux + 0, aux + 3, 0);
if(v[i].size() > 0)
{
aux[0] = 2 * v[i][v[i].size() - 1];
aux[1] = 2 * (M - v[i][0]);
}
aux[2] = min(aux[1], aux[0]);
for(int j = 1; j < v[i].size(); j++)
aux[2] = min(aux[2], 2 * (v[i][j - 1] + M - v[i][j]));
if(i == 1)
{
dp[0][1] = aux[0];
dp[1][1] = MAX;
dp[2][1] = aux[2];
dp[3][1] = dp[5][1] = MAX;
dp[4][1] = M;
continue;
}
dp[0][i] = min(aux[0] + dp[0][i - 1] + D, aux[0] + dp[5][i - 1] + D);
dp[1][i] = min(aux[1] + dp[1][i - 1] + D, aux[1] + dp[4][i - 1] + D);
dp[2][i] = min(aux[2] + dp[0][i - 1] + D, aux[2] + 3 * D + dp[2][i - 1]);
dp[3][i] = min(aux[2] + dp[1][i - 1] + D, aux[2] + 3 * D + dp[3][i - 1]);
dp[4][i] = min(min(dp[0][i - 1] + M + D, dp[2][i - 1] + D * 3 + M),
min(dp[4][i - 1] + D * 3 + aux[2], dp[5][i - 1] + D + M));
dp[5][i] = min(min(dp[1][i - 1] + M + D, dp[3][i - 1] + D * 3 + M),
min(dp[5][i - 1] + D * 3 + aux[2], dp[4][i - 1] + D + M));
dp[0][i] = min(MAX, dp[0][i]);
dp[1][i] = min(MAX, dp[1][i]);
dp[2][i] = min(MAX, dp[2][i]);
dp[3][i] = min(MAX, dp[3][i]);
dp[4][i] = min(MAX, dp[4][i]);
dp[5][i] = min(MAX, dp[5][i]);
}
fout << min(dp[0][N], dp[5][N]);
return 0;
}