Cod sursa(job #122625)

Utilizator alexeiIacob Radu alexei Data 13 ianuarie 2008 11:15:33
Problema Bilute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<fstream>
#define nmax 30002
char k[nmax];
int sol[nmax],sol2[nmax],sol7[nmax];
long long sol3[nmax],sol4[nmax],sol5[nmax],sol6[nmax];
using namespace std;
int main()
{
    ifstream f("bilute.in");
    ofstream g("bilute.out");
 int c1[nmax];
 int n;
 f>>n;                   
int i; 
int val1,val2,sumo=0;
long long ultim=0,ultim1;

 for(i=1; i<=n; ++i)
{  f>>val1>>val2;
 if(val1)
{  c1[i]=val1; 
   sol5[i]=ultim+c1[i];
   ultim=sol5[i];
   sol[i]=val1*val2;
   sol2[i]=sol[i]+sumo;
   sumo=sol2[i];
 }
  else
  { k[i]='0';
  sol5[i]=ultim;
  }   
}
ultim=0;
for(i=n; i>=1; i--){
 if(k[i]!='0'){
sol6[i]=ultim+c1[i];
ultim=sol6[i];}
 else
 sol6[i]=ultim;}

ultim=0;ultim1=0;int j;
 for(i=1; i<=n; ++i)
{  if(k[i]!='0')
         {
         sol3[i]=ultim+c1[i];
         sol3[i]+=sol5[i-1];
         ultim=sol3[i];
         }
   else{
   ultim+=sol5[i-1];
   sol3[i]=ultim;}
}      
 ultim=0,ultim1=0;        
 for(i=n; i>=1; --i){
  if(k[i]!='0'){
                sol4[i]=ultim+c1[i]; 
                sol4[i]+=sol6[i+1];
                ultim=sol4[i];       
                
                sol7[i]=ultim1+sol[i];
                ultim1=sol7[i];}                          
   else{
 ultim+=sol6[i+1];
 sol4[i]=ultim;}
}  

unsigned long long sum,smax=0;
int ibun=0;ultim=0;ultim1=0;
for(i=1; i<=n; i++)
{
 if(k[i]!='0') 
{  sum=0;
         sum+=sol2[i-1];
         sum+=sol3[i-1];
         sum+=sol7[i+1];
         sum+=sol4[i+1];
  if(!smax){
  smax=sum;
  ibun=i;}
  if(sum<smax){
  smax=sum;
  ibun=i;}
}
}
g<<ibun<<" "<<smax<<"\n";
    return 0;
}