Cod sursa(job #136794)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 15 februarie 2008 23:11:51
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#include <limits.h>
int n, C[30001], L[30001], b, dr[30001];
long long cst, cdr, lst, ldr, s, min;

int abs(int i){	return i > 0 ? i : (-i);}

int main()
{
	freopen("bilute.in","r",stdin);
	freopen("bilute.out","w",stdout);
	int i, poz = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)  scanf("%d %d", &C[i], &L[i]);	
  
    for (i = 2; i <= n; i ++) 
	{  
        ldr += C[i] * L[i];  
        cdr += C[i] * (i - 1);  
    }  
  
    for (i = n; i >= 1; i --)   dr[i] = dr[i + 1] + C[i];  
  
    min = cdr + ldr;   b = 1;  
  
    for (i = 2; i <= n; i ++) 
	{  
        lst += C[i - 1] * L[i - 1];  
        ldr -= C[i] * L[i];  
  
        s += C[i - 1];  
  
        cst += s;  
        cdr -= dr[i];  
  
        if (lst + cst + ldr + cdr < min) 
		{  
            min = lst + cst + ldr + cdr;  
			b = i;  
        }  
    }  
  
    printf("%d %lld\n", b, min);  
  
    return 0;  
}