Cod sursa(job #1549189)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 decembrie 2015 00:39:27
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

#define DIM 32000
using namespace std;

int N, P; long long S, M;
long long A[DIM], B[DIM], C[DIM];
long long D[DIM], E[DIM], L[DIM];

int main () {

    freopen ("bilute.in" ,"r", stdin );
    freopen ("bilute.out","w", stdout);

    scanf ("%d", &N);
    for (int i = 1; i <= N; i ++) {
        scanf ("%lld %lld", &E[i], &L[i]);
        S += E[i] * L[i];
    }

    for (int i = 1; i <= N; i ++) {
        A[i] = A[i-1] + E[i];
        B[i] = B[i-1] + A[i];
    }

    for (int i = N; i >= 1; i --) {
        C[i] = C[i+1] + E[i];
        D[i] = D[i+1] + C[i];
    }

    M = 1000000000000000000LL;
    for (int i = 1; i <= N; i ++) {
        if (M > S - E[i] * L[i] + B[i-1] + D[i+1]) {
            M = S - E[i] * L[i] + B[i-1] + D[i+1];
            P = i;
        }
    }

    printf ("%d %lld\n", P, M);

    return 0;
}