Cod sursa(job #253977)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 6 februarie 2009 13:58:21
Problema Caramizi Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.53 kb
#include<fstream.h>
#include<math.h>

long  sw,aux,l,s,max,x,n,m,i,j,p,q,k;

long long suma[150000],v1[150000],v2[150000],a[150000];


void urca(int k)
	{
	while ((k/2>0) && (a[k/2]>a[k]))
		{
		aux=a[k];
		a[k]=a[k/2];
		a[k/2]=aux;;
		k/=2;
		}
	}

void coboara (int k)
	{
	i=1;
	sw=1;
	while ((2*i<=k) &&(sw))
		{
		sw=0;
		if (2*i+1<=k) {
			      if (a[2*i+1]>a[2*i])
						{
						if (a[2*i]<a[i])
							{
							aux=a[2*i];
							a[2*i]=a[i];
							a[i]=aux;
							i*=2;
							sw=1;
							}
						}
					else
						{
						if (a[2*i+1]<a[i])
							{
							aux=a[2*i+1];
							a[2*i+1]=a[i];
							a[i]=aux;
							i=i*2+1;
							sw=1;
							}
						}
			      }
			else if (a[2*i]<a[i]){
					     aux=a[i];
					     a[i]=a[2*i];
					     a[2*i]=aux;
					     i*=2;
					     sw=1;
					     }
		}

	}


int main()
{
ifstream f("caramizi.in");
f>>n>>m;
k=0;
for (i=1;i<=n;i++)
	{
	f>>x;
	a[++k]=x;
	urca (k);
	}
p=0;
while (k)
	{
	v1[++p]=a[1];
	a[1]=a[k--];
	coboara(k);
	}
k=0;
for (i=1;i<=m;i++)
	{
	f>>x;
	a[++k]=x;
	urca(k);
	}

f.close();
p=0;
while (k)
	{
	v2[++p]=a[1];
	a[1]=a[k--];
	coboara(k);
	}
suma[1]=v1[1];
for (i=2;i<=n;i++)
	suma[i]=suma[i-1]+v1[i];
k=1;
p=0;
q=1;
max=n;


v1[n+1]=pow(2,63);


ofstream g("caramizi.out");
while (k<=v2[m])
	{
	if (k>v1[p+1]) p++;
	s=k*(n-p)+(suma[p]/k)*k;
	if (s>max) max=s;
		else s=max;
	if (k==v2[q]) g<<max<<'\n';
	if (k==v2[q]) q++;
        k++;
	}
g.close();
return 0;
}