Cod sursa(job #1984873)

Utilizator robx12lnLinca Robert robx12ln Data 26 mai 2017 12:58:42
Problema Magazin Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define DIM 100000
#define INF (1LL<<50)
using namespace std;
ifstream fin("magazin.in");
ofstream fout("magazin.out");
long long aux1[DIM], aux2[DIM], aux3[DIM], D[DIM][6];
int 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], 2LL * ( 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;
}