Pagini recente » Cod sursa (job #1438827) | Cod sursa (job #760303) | Cod sursa (job #313010) | Cod sursa (job #2063484) | Cod sursa (job #2405753)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 3 * 1e3 + 1e2;
ifstream in("magazin.in");
ofstream out("magazin.out");
vector < int > v[1 + NMAX];
int dp[NMAX][2][3];
int cost[2][2];
int P, n, m;
int d, i, j;
int k , x, y;
int ans;
void check11(int &a, int b) {
a = min(a, b);
}
int main()
{
in>>P>>n>>m>>d;
for(i=1; i<=P; i++) {
in>>x>>y;
v[x].push_back(y);
}
for(i=0; i<2; i++)
for(j=0; j<3; j++)
dp[0][i][j] = (1 << 30);
dp[0][0][0] = -d;
for(i=1; i<=n; i++) {
sort(v[i].begin(),v[i].end());
if(v[i].empty()) {
for(j=0; j<2; j++)
for(k=0; k<2; k++)
cost[j][k]=0;
} else {
cost[0][0]=2*v[i].back();
cost[1][0]=2*(m+1-v[i].front());
cost[0][1]=cost[1][1]=min(cost[0][0],cost[1][0]);
for(j=0; j+1<v[i].size(); j++)
cost[0][1]=min(cost[0][1],2*v[i][j]+2*(m+1-v[i][j+1]));
for(j=0; j+1<v[i].size(); j++)
cost[1][1]=min(cost[1][1],2*v[i][j]+2*(m+1-v[i][j+1]));
}
for(j=0; j<2; j++)
for(k=0; k<3; k++)
dp[i][j][k]=(1<<30);
for(j=0; j<2; j++) {
check11(dp[i][j][0],dp[i-1][j][0]+d+cost[j][0]);
check11(dp[i][j][0],dp[i-1][(1-j)][0]+d+m+1);
check11(dp[i][j][0],dp[i-1][(1-j)][2]+3*d+m+1);
check11(dp[i][j][0],dp[i-1][j][2]+3*d+2*(m+1));
check11(dp[i][j][0],dp[i-1][j][1]+d+cost[j][0]);
check11(dp[i][j][1],dp[i-1][j][1]+3*d+cost[j][1]);
check11(dp[i][j][1],dp[i-1][j][0]+2*(m+1)+d);
check11(dp[i][j][1],dp[i-1][j][2]+2*(m+1)+3*d);
check11(dp[i][j][1],dp[i-1][(1-j)][0]+(m+1)+d);
check11(dp[i][j][1],dp[i-1][(1-j)][2]+(m+1)+3*d);
check11(dp[i][j][2],dp[i-1][j][0]+d+cost[j][1]);
check11(dp[i][j][2],dp[i-1][j][1]+d+cost[j][1]);
check11(dp[i][j][2],dp[i-1][j][2]+3*d+cost[j][1]);
dp[i][j][0]=min(dp[i][j][0],dp[i][j][1]);
}
}
ans = min(dp[n][0][0], dp[n][0][1]);
out << ans << '\n';
in.close();
out.close();
return 0;
}