Cod sursa(job #117764)

Utilizator DastasIonescu Vlad Dastas Data 22 decembrie 2007 11:34:49
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>

const int maxn = 30001;

FILE *in = fopen("bilute.in","r"), *out = fopen("bilute.out","w");

struct bila
{
    int c, l;
};

int n;
bila a[maxn];

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d %d", &a[i].c, &a[i].l);
}

int myabs(int x)
{
    return x < 0 ? -x : x;
}

int t[maxn]; // t[i] = timpul minim pt a colora toate 1...i-1 in i;
int lt[maxn]; // lt[i] = suma tuturor a[i].c

int p[maxn]; // p[i] = timpul minim pt a colora toate i+1...n in i;
             // raspunsul va fi i pt care t[i] + p[i] e minim     ;
int lp[maxn]; // ... numai invers

int main()
{
    read();

    int min = 1 << 29;
    int answ = 0;


    for ( int i = 1; i <= n; ++i )
        lt[i] = lt[i-1] + a[i].c;
    for ( int i = n; i; --i )
        lp[i] = lp[i+1] + a[i].c;

    for ( int i = 1; i <= n; ++i )
        t[i] = t[i-1] + a[i-1].c * a[i-1].l + lt[i-1];

    for ( int i = n; i ; --i )
        p[i] = p[i+1] + a[i+1].c * a[i+1].l + lp[i+1];

    for ( int i = 1; i <= n; ++i )
        if ( t[i] + p[i] < min )
            min = t[i] + p[i], answ = i;

    fprintf(out, "%d %d\n", answ, min);

	return 0;
}