Cod sursa(job #117872)

Utilizator dominoMircea Pasoi domino Data 22 decembrie 2007 16:03:16
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>

#define MAX_N 30005
#define FIN "bilute.in"
#define FOUT "bilute.out"
#define ll long long

int N, C[MAX_N], L[MAX_N], S[MAX_N], CL, pos;
ll res;

int main(void)
{
    int i;
    ll left, right, t;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
    {
        scanf("%d %d", C+i, L+i);
        CL += C[i]*L[i];
        S[i] = S[i-1]+C[i];
    }

    left = right = 0;
    for (i = 2; i <= N; ++i)
        right += (ll)(i-1)*C[i];
    res = CL-C[1]*L[1]+right;
    for (i = 2; i <= N; ++i)
    {
        right -= C[i];
        right -= S[N]-S[i];
        left += S[i-1];
        t = CL-C[i]*L[i]+left+right;
        if (res > t) res = t, pos = i;
    }
    printf("%d %lld\n", pos, res);

    return 0;
}