Cod sursa(job #1979774)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 11 mai 2017 13:09:59
Problema Magazin Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.67 kb
/*
    dp[i][0] = plec de jos si ajung jos
    dp[i][1] = plec de sus si ajung sus

    dp[i][2] = plec de jos, ajung sus iar traseul este neconex
    dp[i][3] = plec de sus, ajung jos iar traseul este neconex

    dp[i][4] = plec de jos, ajung sus iar traseul este conex
    dp[i][5] = plec de sus, ajung jos iar traseul este conex
*/
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "magazin.in"  );
ofstream out( "magazin.out" );

const int DIM = 3e4 + 5;
const int INF = 0x3f3f3f3f;

vector<int> lst[DIM];
int dp[DIM][6], aux[DIM][3];

int main( void ) {

    int p, n, m, d;
    in >> p >> n >> m >> d; m ++;

    for( int i = 1; i <= p; i ++ ) {
        int x, y;
        in >> x >> y;

        lst[x].push_back( y );
    }

    for( int i = 1; i <= n; i ++ ) {
        sort( lst[i].begin(), lst[i].end() );

        if( lst[i].size() >= 1 ) {
            aux[i][0] = 2 * lst[i].back();
            aux[i][1] = 2 * ( m - lst[i].front() );
        }

        aux[i][2] = min( aux[i][0], aux[i][1] );
        for( int j = 1; j < lst[i].size(); j ++ )
            aux[i][2] = min( aux[i][2], 2 * ( m - ( lst[i][j] - lst[i][j - 1] ) ) );

        if( i == 1 ) {
            dp[i][0] = aux[i][0]; dp[i][1] = INF;
            dp[i][2] = aux[i][2]; dp[i][3] = INF;
            dp[i][4] = m;         dp[i][5] = INF;
        }
        else {
            dp[i][0] = min( dp[i - 1][0] + d + aux[i][0],
                            dp[i - 1][5] + d + aux[i][0] );

            dp[i][1] = min( dp[i - 1][1] + d + aux[i][1],
                            dp[i - 1][4] + d + aux[i][1] );

            dp[i][2] = min( dp[i - 1][0] + d + aux[i][2],
                            dp[i - 1][2] + (d * 3) + aux[i][2] );

            dp[i][3] = min( dp[i - 1][1] + d + aux[i][2],
                            dp[i - 1][3] + (d * 3) + aux[i][2] );

            dp[i][4] = min( min( dp[i - 1][0] + d + m,
                                 dp[i - 1][2] + (d * 3) + m ),
                            min( dp[i - 1][4] + (d * 3) + aux[i][2],
                                 dp[i - 1][5] + d + m ) );

            dp[i][5] = min( min( dp[i - 1][1] + d + m,
                                 dp[i - 1][3] + (d * 3) + m ),
                            min( dp[i - 1][4] + d + m,
                                 dp[i - 1][5] + (d * 3) + aux[i][2] ) );

            dp[i][0] = min( dp[i][0], INF ); dp[i][1] = min( dp[i][1], INF );
            dp[i][2] = min( dp[i][2], INF ); dp[i][3] = min( dp[i][3], INF );
            dp[i][4] = min( dp[i][4], INF ); dp[i][5] = min( dp[i][5], INF );
        }
    }

    out << min( dp[n][0], dp[n][5] ) << endl;
    return 0;
}