Cod sursa(job #167195)

Utilizator jupanu92Anonim jupanu92 Data 29 martie 2008 10:31:08
Problema Bilute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
using namespace std;
int n, C[30001], L[30001], b, dr[30001];
unsigned long cst, cdr, lst, ldr, s, min;

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

int main()
{
	ifstream fin("bilute.in");
	ofstream fout("bilute.out");
	int i, poz = 0;
	fin>>n;
	for (i = 1; i <= n; i++)  fin>>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;  
        }  
    }  
  
    fout<<b<<" "min;  
  
    return 0;  
}