Pagini recente » Cod sursa (job #683732) | Cod sursa (job #402692) | Cod sursa (job #1669742) | Cod sursa (job #1841874) | Cod sursa (job #2391006)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=30005;
vector<int> v[nmax];
int cost[2][2];
int dp[nmax][2][3];
int P,n,m,d,i,j,k,x,y,ans;
void prp(int &a,int b)
{
a=min(a,b);
}
int main()
{
ifstream f("magazin.in");
ofstream g("magazin.out");
f>>P>>n>>m>>d;
for(i=1;i<=P;i++)
{
f>>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);
//0-normal
//1-a fost inchis
//2-trebuie inchis
for(j=0;j<2;j++)
{
prp(dp[i][j][0],dp[i-1][j][0]+d+cost[j][0]);
prp(dp[i][j][0],dp[i-1][(1-j)][0]+d+m+1);
prp(dp[i][j][0],dp[i-1][(1-j)][2]+3*d+m+1);
prp(dp[i][j][0],dp[i-1][j][2]+3*d+2*(m+1));
prp(dp[i][j][0],dp[i-1][j][1]+d+cost[j][0]);
prp(dp[i][j][1],dp[i-1][j][1]+3*d+cost[j][1]);
prp(dp[i][j][1],dp[i-1][j][0]+2*(m+1)+d);
prp(dp[i][j][1],dp[i-1][j][2]+2*(m+1)+3*d);
prp(dp[i][j][1],dp[i-1][(1-j)][0]+(m+1)+d);
prp(dp[i][j][1],dp[i-1][(1-j)][2]+(m+1)+3*d);
prp(dp[i][j][2],dp[i-1][j][0]+d+cost[j][1]);
prp(dp[i][j][2],dp[i-1][j][1]+d+cost[j][1]);
prp(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]);
g<<ans;
return 0;
}