Cod sursa(job #2005880)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 28 iulie 2017 13:55:53
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
/*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;
}