Cod sursa(job #122446)

Utilizator alexeiIacob Radu alexei Data 12 ianuarie 2008 14:30:11
Problema Bilute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
#define nmax 30001
#define inf 452985000
char k[nmax];
int sol[nmax],sol2[nmax],sol7[nmax];
long long sol3[nmax],sol4[nmax],sol5[nmax],sol6[nmax];
int main()
{
    
 freopen("bilute.in","r",stdin);
 freopen("bilute.out","w",stdout);
 int c1[nmax];
 int n;
long long smax=inf;
 scanf("%d",&n);   
int i,j; 
char naspa='0';
int val1,val2,sumo=0;
 for(i=1; i<=n; ++i)
{  scanf("%d%d",&val1,&val2);
 if(val1)
{  c1[i]=val1; 
   sol5[i]=sol5[i-1]+c1[i];
   sol[i]=val1*val2;
   sol2[i]=sol[i]+sumo;
   sumo=sol2[i];
 }
  else
  { k[i]='0'; naspa='1';  }   
}

for(i=n; i>=1; i--)
sol6[i]=sol6[i+1]+c1[i];

 for(i=1; i<=n; ++i)
 sol3[i]=sol3[i-1]+sol5[i-1]+c1[i];
 for(i=n; i>=1; --i){
 sol4[i]=sol4[i+1]+sol6[i+1]+c1[i]; 
 sol7[i]=sol7[i+1]+sol[i];}

long long sum;
int ibun;
for(i=1; i<=n; i++)
{
 if(k[i]!='0') 
{  sum=sol2[i-1]+sol7[i+1]+sol3[i-1]+sol4[i+1];  
  if(sum<smax){
  smax=sum;
  ibun=i;}
}
}

printf("%d %lld\n",ibun,smax);    
    
    return 0;
}