Pagini recente » Cod sursa (job #1310944) | Cod sursa (job #2953576) | Cod sursa (job #1871389) | Cod sursa (job #239630) | Cod sursa (job #1979761)
/*
dp[i][0] = plec de jos si ajung jos
dp[i][1] = plec de sus si ajung sus
dp[i][2] = plec de jos, ajung sus iar traseul este neconex
dp[i][3] = plec de sus, ajung jos iar traseul este neconex
dp[i][4] = plec de jos, ajung sus iar traseul este conex
dp[i][5] = plec de sus, ajung jos iar traseul este conex
*/
#include <bits/stdc++.h>
using namespace std;
ifstream in ( "magazin.in" );
ofstream out( "magazin.out" );
const int DIM = 3e4 + 5;
vector<int> lst[DIM];
int dp[DIM][6], aux[DIM][3];
int main( void ) {
int p, n, m, d;
in >> p >> n >> m >> d; m ++;
for( int i = 1; i <= p; i ++ ) {
int x, y;
in >> x >> y;
lst[x].push_back( y );
}
for( int i = 1; i <= n; i ++ ) {
sort( lst[i].begin(), lst[i].end() );
if( lst[i].size() >= 1 ) {
aux[i][0] = 2 * lst[i].back();
aux[i][1] = 2 * ( m - lst[i].front() );
}
aux[i][2] = min( aux[i][0], aux[i][1] );
for( int j = 1; j < lst[i].size(); j ++ )
aux[i][2] = min( aux[i][2], 2 * ( m - ( lst[i][j] - lst[i][j - 1] ) ) );
dp[i][0] = min( dp[i - 1][0] + d + aux[i][0],
dp[i - 1][5] + d + aux[i][0] );
dp[i][1] = min( dp[i - 1][1] + d + aux[i][1],
dp[i - 1][4] + d + aux[i][1] );
dp[i][2] = min( dp[i - 1][0] + d + aux[i][2],
dp[i - 1][2] + (d * 3) + aux[i][2] );
dp[i][3] = min( dp[i - 1][1] + d + aux[i][2],
dp[i - 1][3] + d + aux[i][2] );
dp[i][4] = min( min( dp[i - 1][0] + d + m,
dp[i - 1][2] + (d + 3) + m ),
min( dp[i - 1][4] + (d * 3) + aux[i][2],
dp[i - 1][5] + d + m ) );
dp[i][5] = min( min( dp[i - 1][1] + d + m,
dp[i - 1][3] + (d * 3) + m ),
min( dp[i - 1][4] + d + m,
dp[i - 1][5] + (d * 3) + aux[i][2] ) );
}
out << min( dp[n][0], dp[n][5] ) << endl;
return 0;
}