Cod sursa(job #2405753)

Utilizator NeredesinI am not real Neredesin Data 14 aprilie 2019 20:47:24
Problema Magazin Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#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;
}