Pagini recente » Cod sursa (job #2375518) | Cod sursa (job #129584) | Cod sursa (job #2759885) | Cod sursa (job #442801) | Cod sursa (job #1984871)
#include<fstream>
#include<algorithm>
#include<vector>
#define DIM 100000
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("magazin.in");
ofstream fout("magazin.out");
int aux1[DIM], aux2[DIM], aux3[DIM], D[DIM][6], n, m, p, d, a, b;
vector<int> v[DIM];
int main(){
fin >> p >> n >> m >> d;
m++;
for( int i = 1; i <= p; i++ ){
fin >> a >> b;
v[a].push_back( b );
}
for( int i = 1; i <= n; i++ ){
if( v[i].size() == 0 )
continue;
sort( v[i].begin(), v[i].end() );
aux1[i] = 2 * v[i].back();
aux2[i] = 2 * ( m - v[i].front() );
aux3[i] = min( aux1[i], aux2[i] );
for( int j = 1; j < v[i].size(); j++ ){
aux3[i] = min( aux3[i], 2 * ( m - v[i][j] + v[i][j - 1] ) );
}
}
D[1][0] = aux1[1];
D[1][2] = aux3[1];
D[1][4] = m;
D[1][1] = D[1][3] = D[1][5] = INF;
for( int i = 2; i <= n; i++ ){
D[i][0] = d + aux1[i] + min( D[i - 1][0], D[i - 1][5] );
D[i][1] = d + aux2[i] + min( D[i - 1][1], D[i - 1][4] );
D[i][2] = min( D[i - 1][0] + d + aux3[i], min( D[i - 1][2] + 3 * d + aux3[i], D[i - 1][5] + d + aux3[i] ) );
D[i][3] = min( D[i - 1][1] + d + aux3[i], min( D[i - 1][3] + 3 * d + aux3[i], D[i - 1][4] + d + aux3[i] ) );
D[i][4] = min( min( D[i - 1][4] + 3 * d + aux2[i], D[i - 1][0] + d + m ), min( D[i - 1][2] + 3 * d + m, D[i - 1][5] + d + m ) );
D[i][5] = min( min( D[i - 1][5] + 3 * d + aux2[i], D[i - 1][1] + d + m ), min( D[i - 1][3] + 3 * d + m, D[i - 1][4] + d + m ) );
}
fout << min( D[n][0], D[n][5] ) << "\n";
return 0;
}