Cod sursa(job #122519)

Utilizator alexeiIacob Radu alexei Data 12 ianuarie 2008 17:51:27
Problema Bilute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<fstream>
using namespace std;
#define nmax 30001
char k[nmax];
int sol[nmax],sol2[nmax],sol7[nmax];
long long sol3[nmax],sol4[nmax],sol5[nmax],sol6[nmax];
int main()
{
    ifstream f("bilute.in");
    ofstream g("bilute.out");
 int c1[nmax];
 int n;
 f>>n;                   
int i; 
int val1,val2,sumo=0;
 for(i=1; i<=n; ++i)
{  f>>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';}   
}

long long ultim,ultim1;
ultim=0;

for(i=n; i>=1; i--)
 if(k[i]!='0'){
sol6[i]=ultim+c1[i];
ultim=sol6[i];}

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

j=i;
   if(i!=1){
           while(!sol2[j-1])
            --j; }
sum+=sol2[j-1];
sum+=sol3[j-1];
j=i; 
   if(i!=n){
          while(!sol7[j+1])
            ++j;}
sum+=sol7[j+1];
sum+=sol4[j+1];

  if(!smax)
  smax=sum;
  if(sum<smax){
  smax=sum;
  ibun=i;}
}


}
g<<ibun<<" "<<smax<<"\n";
    return 0;
}