Cod sursa(job #25552)

Utilizator flo_demonBunau Florin flo_demon Data 4 martie 2007 12:54:47
Problema Magazin Scor 15
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.76 kb
#include <stdio.h>
#include <iostream>

using namespace std;

#define MAX 30006
#define INF 99999999

bool c[MAX];
int maxx[MAX], minn[MAX], culoar, raft, n, m, p, d;
int a[MAX][2], cost[MAX][2];

int main()
{
    FILE *fin = fopen("magazin.in", "r");
    fscanf(fin, "%d%d%d%d", &p, &n, &m, &d);
    for (int i = 1; i <= n+2; ++i)
    {
        maxx[i] = 0;
        minn[i] = INF;
        cost[i][0] = INF;
        cost[i][1] = INF;
    }
    for (int i = 1; i <= p; ++i)
    {
        fscanf(fin, "%d%d", &culoar, &raft);
        if (maxx[culoar] < raft)
            maxx[culoar] = raft;
        if (minn[culoar] > raft)
            minn[culoar] = raft;
        c[culoar] = true;
    }
    fclose(fin);
    
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            a[i][0] = 0;
            a[i][1] = 0;
        }
        else
        {
            a[i][0] = 2*(maxx[i]-1);
            a[i][1] = 2*(m-minn[i]);
        }
    }
    
    
    if (c[1])
    {
        cost[1][0] = a[1][0] + 2;
        cost[1][1] = m + 1;
    }
    else
    {
        cost[1][0] = 0;
        cost[1][1] = 1 + m;
    }
    for (int i = 2; i <= n; ++i)
    {
        if (cost[i][0] > cost[i-1][0] + d + 2 + a[i][0])
            cost[i][0] = cost[i-1][0] + d + 2 + a[i][0];
        if (cost[i][1] > cost[i-1][1] + d + 2 + a[i-1][1])
            cost[i][1] = cost[i-1][1] + d + 2 + a[i-1][1];
        if (cost[i][1] > cost[i-1][0] + d + 1 + m)
            cost[i][1] = cost[i-1][0] + d + 1 + m;
        if (cost[i][0] > cost[i-1][1] + d + 1 + m)
            cost[i][0] = cost[i-1][1] + d + 1 + m;
    }
    
    FILE *fout = fopen("magazin.out", "w");
    fprintf(fout, "%d\n", cost[n][0]);
    fclose(fout);
    
    return 0;
}