Pagini recente » Cod sursa (job #404138) | Cod sursa (job #1906849) | Cod sursa (job #3195294) | Cod sursa (job #2881534) | Cod sursa (job #2879400)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("magazin.in");
ofstream fout("magazin.out");
int p,n,m,d;
int bnt[30005],best[2][30005],dp[30005][2][3];
vector <int> v[30005];
int main()
{
fin>>p>>n>>m>>d;
for(int i=1; i<=p; i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
}
m++;
for(int i=1; i<=n; i++)
{
if(v[i].empty())
continue;
sort(v[i].begin(),v[i].end());
bnt[i]=min(2*v[i].back(),2*(m-v[i].front()));
for(int j=0; j<v[i].size()-1; j++)
bnt[i]=min(bnt[i],2*(m-v[i][j+1]+v[i][j]));
best[0][i]=2*v[i].back();
best[1][i]=2*(m-v[i].front());
}
dp[1][0][0]=best[0][1];
dp[1][0][1]=bnt[1];
dp[1][0][2]=2*m;
dp[1][1][0]=1e9;
dp[1][1][1]=1e9;
dp[1][1][2]=m;
for(int i=2; i<=n; i++)
{
for(int j=0; j<2; j++)
{
dp[i][j][0]=min(dp[i-1][j][0]+d+best[j][i],
dp[i-1][j][2]+d+best[j][i]);
dp[i][j][1]=min({dp[i-1][j][0]+d+bnt[i],
dp[i-1][j][1]+3*d+bnt[i],
dp[i-1][j][2]+d+bnt[i]});
dp[i][j][2]=min({dp[i-1][j][0]+d+2*m,
dp[i-1][j][1]+3*d+2*m,
dp[i-1][j][2]+3*d+bnt[i],
dp[i-1][j][2]+d+2*m,
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});
}
}
fout<<min(dp[n][0][0],dp[n][0][2])<<"\n";
return 0;
}