Cod sursa(job #24608)

Utilizator dominoMircea Pasoi domino Data 3 martie 2007 00:02:32
Problema Magazin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 30005
#define FIN "magazin.in"
#define FOUT "magazin.out"
#define INF 0x3f3f3f3f
#define FOR(i, a, b) for (i = (a); i < (int)(b); i++)

int P, N, A, B, V1[MAX_N], V2[MAX_N], V3[MAX_N], C[MAX_N][6], Res = INF;
vector<int> G[MAX_N];

int main(void)
{
    int i, j, t, a, b;
    
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d %d", &P, &N, &A, &B);

    FOR (i, 0, P)
    {
        scanf("%d %d", &a, &b), a--;
        G[a].push_back(b);
    }
    FOR (i, 0, N) sort(G[i].begin(), G[i].end());

    FOR (i, 0, N)
    {
         if (!G[i].size()) { V1[i] = V2[i] = B; V3[i] = 3*B; continue; }
         V1[i] = B + 2*G[i][G[i].size()-1];
         V2[i] = B + 2*(A+1-G[i][0]);
         V3[i] = min(V1[i], V2[i])+2*B;
         FOR (j, 0, G[i].size()-1)
         {
            t = 2*G[i][j] + 2*(A+1-G[i][j+1]) + 3*B;
            V3[i] = min(V3[i], t);
         }
    }

    memset(C, 0x3f, sizeof(C));
    C[0][0] = V1[0]-B; C[0][1] = 2*(A+1); C[0][2] = min(V2[0]-B, V3[0]-3*B);
    C[0][3] = INF; C[0][4] = A+1; C[0][5] = INF;
    FOR (i, 1, N)
    {
        // 0
        C[i][0] =  min(C[i][0], C[i-1][0] + V1[i]);
        C[i][0] =  min(C[i][0], C[i-1][1] + V1[i]);
        C[i][0] =  min(C[i][0], C[i-1][2] + 2*(A+1) + V1[i]);
        C[i][0] =  min(C[i][0], C[i-1][3] + (A+1) + V1[i]);
        C[i][0] =  min(C[i][0], C[i-1][4] + (A+1) + V1[i]);
        C[i][0] =  min(C[i][0], C[i-1][5] + (A+1) + V1[i]);

        C[i][1] =  min(C[i][1], C[i-1][0] + B + 2*(A+1));
        C[i][1] =  min(C[i][1], C[i-1][1] + min(min(V1[i],V2[i])+2*B, V3[i]));
        C[i][1] =  min(C[i][1], C[i-1][2] + B + 2*(A+1));
        C[i][1] =  min(C[i][1], C[i-1][3] + B + (A+1));
        C[i][1] =  min(C[i][1], C[i-1][4] + B + (A+1));
        C[i][1] =  min(C[i][1], C[i-1][5] + 3*B + (A+1));

        C[i][2] =  min(C[i][2], C[i-1][0] + min(V2[i], V3[i]-2*B));
        C[i][2] =  min(C[i][2], C[i-1][1] + min(V2[i], V3[i]-2*B));
        C[i][2] =  min(C[i][2], C[i-1][2] + min(min(V1[i], V2[i])+2*B, V3[i]));
        C[i][2] =  min(C[i][2], C[i-1][3] + min(V2[i], V3[i]-2*B) + (A+1));
        C[i][2] =  min(C[i][2], C[i-1][4] + min(V2[i], V3[i]-2*B) + (A+1));
        C[i][2] =  min(C[i][2], C[i-1][5] + min(V2[i], V3[i]-2*B) + (A+1));

        // 1
        C[i][3] =  min(C[i][3], C[i-1][3] + V2[i]);
        C[i][3] =  min(C[i][3], C[i-1][4] + V2[i]);
        C[i][3] =  min(C[i][3], C[i-1][5] + 2*(A+1) + V2[i]);
        C[i][3] =  min(C[i][3], C[i-1][0] + (A+1) + V2[i]);
        C[i][3] =  min(C[i][3], C[i-1][1] + (A+1) + V2[i]);
        C[i][3] =  min(C[i][3], C[i-1][2] + (A+1) + V2[i]);

        C[i][4] =  min(C[i][4], C[i-1][3] + B + 2*(A+1));
        C[i][4] =  min(C[i][4], C[i-1][4] + min(min(V1[i], V2[i])+2*B, V3[i]));
        C[i][4] =  min(C[i][4], C[i-1][5] + B + 2*(A+1));
        C[i][4] =  min(C[i][4], C[i-1][0] + B + (A+1));
        C[i][4] =  min(C[i][4], C[i-1][1] + B + (A+1));
        C[i][4] =  min(C[i][4], C[i-1][2] + 3*B + (A+1));

        C[i][5] =  min(C[i][5], C[i-1][3] + min(V1[i], V3[i]-2*B));
        C[i][5] =  min(C[i][5], C[i-1][4] + min(V1[i], V3[i]-2*B));
        C[i][5] =  min(C[i][5], C[i-1][5] + min(min(V1[i], V2[i])+2*B, V3[i]));
        C[i][5] =  min(C[i][5], C[i-1][0] + min(V1[i], V3[i]-2*B) + (A+1));
        C[i][5] =  min(C[i][5], C[i-1][1] + min(V1[i], V3[i]-2*B) + (A+1));
        C[i][5] =  min(C[i][5], C[i-1][2] + min(V1[i], V3[i]-2*B) + (A+1));

    }
    Res = min(C[N-1][0], C[N-1][1]);

    printf("%d\n", Res);
    
    return 0;
}