Cod sursa(job #137622)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 17 februarie 2008 12:49:29
Problema Stalpi Scor 20
Compilator c Status done
Runda preONI 2008, Runda 4, Clasa a 10-a Marime 1.82 kb
#include <stdio.h>
#define NMAX (1<<17)
#define MIN(a,b) (((a)<(b))?(a):(b))

int N;
long long A[NMAX], C[NMAX], X[NMAX], D[NMAX], S[NMAX], LLINF;

void read()
{
        int i;

        freopen("stalpi.in", "r", stdin);
        scanf("%d", &N);

        for (i = 1; i <= N; i++)
            scanf("%lld%lld%lld%lld", X+i, C+i, S+i, D+i);
}

void brut()
{
        int i, j, k1, k2, p, q, md;
        long long d=2147483647, aux;

        for (i = 1; i <= N; i++)
            for (j = i+1; j <= N; j++)
                if (X[i]>X[j])
                {
                   aux = X[i], X[i] = X[j], X[j] = aux;
                   aux = C[i], C[i] = C[j], C[j] = aux;
                   aux = S[i], S[i] = S[j], S[j] = aux;
                   aux = D[i], D[i] = D[j], D[j] = aux;
                }

        LLINF = d*d;

        X[0] = X[1]-1;
        X[N+1] = X[N]+1;
        A[1] = C[1];
        for (i = 2; i <= N+1; i++)
        {
            A[i] = LLINF;
            for (j = 0; j < i; j++)
            {
                p = j; q = N+1;
                d = X[j]+D[j];
                k1 = j;

                while (q-p>=0)
                {
                        md = (p+q)>>1;
                        if (X[md]>d) q = md-1;
                        else p = md+1, k1 = md;
                }

                p = 0; q = i;
                d = X[i]-S[i];
                k2 = i;

                while (q-p>=0)
                {
                        md = (p+q)>>1;
                        if (X[md]<d) p = md+1;
                        else q = md-1, k2 = md;
                }

                if (k1>=k2-1)
                   A[i] = MIN(A[i], A[j]+C[i]);
            }
        }
}

void write()
{
        freopen("stalpi.out", "w", stdout);
        printf("%d\n", A[N+1]);
}

int main()
{
        read();
        brut();
        write();
        return 0;
}