Cod sursa(job #167367)

Utilizator jupanu92Anonim jupanu92 Data 29 martie 2008 15:27:12
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;

int C[30001], L[30001],dr[30001];


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

int main()
{long long cst=0,n=0,b=0, cdr=0, lst=0, ldr=0, s=0, min=0;
    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;
}