Pagini recente » Cod sursa (job #1967524) | Cod sursa (job #2853944) | Cod sursa (job #3292068) | Mexitate | Cod sursa (job #2005880)
/*St[i] suma |i-j|*C[i] pt fiecare j din stanga i curent
Dr[i] acelasi lucru dar din partea dreapta
Stl[i],Drl[i] siruri de sume partiale ale sirului L[i]
Calculez pt fiecare i de la 1 la n costul minim cu care
pot sa transform toate bilele in nuanta i, in O(1) cu
ajutorul sirurilor de mai sus (St[i-1]+Dr[i+1]+Stl[i-1]+Drl[i+1]).
Complexitate finala O(n)
(C)2017 Andrei Cotor, Zalau,SJ,RO. All rights reserved.
*/
#include<fstream>
using namespace std;
ifstream fi("bilute.in");
ofstream fo("bilute.out");
int n,i,c,l,Stl[30001],Drl[30001],ind;
long long x,minim,St[30001],Dr[30001];
int main()
{
fi>>n;
for(i=1; i<=n; i++)
{
fi>>c>>l;
St[i+1]=2*St[i]+c-St[i-1];
Stl[i]=Stl[i-1]+l*c;
}
for(i=n; i>=1; i--)
{
c=St[i+1]+St[i-1]-2*St[i];
l=Stl[i]-Stl[i-1];
Dr[i-1]=2*Dr[i]+c-Dr[i+1];
Drl[i]=Drl[i+1]+l;
}
minim=10000000000000LL;
for(i=1; i<=n; i++)
{
x=St[i]+Dr[i]+Stl[i-1]+Drl[i+1];
if(x<minim)
{
ind=i;
minim=x;
}
}
fo<<ind<<" "<<minim<<"\n";
fi.close();
fo.close();
return 0;
}