Pagini recente » Cod sursa (job #3192034) | Cod sursa (job #1272983) | Cod sursa (job #678413) | Cod sursa (job #316645) | Cod sursa (job #122598)
Cod sursa(job #122598)
#include<fstream>
#define nmax 30001
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;
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>1)
--j; }
sum+=sol2[j-1];
sum+=sol3[j-1];
j=i;
if(i!=n){
while(!sol7[j+1]&&j<n)
++j;}
sum+=sol7[j+1];
sum+=sol4[j+1];
if(!smax){
smax=sum;
ibun=i;}
if(sum<smax){
smax=sum;
ibun=i;}
}
}
g<<ibun<<" "<<smax<<"\n";
return 0;
}