Cod sursa(job #253910)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 6 februarie 2009 13:35:52
Problema Caramizi Scor 15
Compilator c Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 2.42 kb
#include<stdio.h>
#define infile "caramizi.in"
#define outfile "caramizi.out"
#define nmax (200*1000+1)
int v[nmax]; //numarul de caramizi de fiecare tip
long long t[nmax]; //t[i]-numarul de turnuri ce se pot face de inaltime i
int n; //numarul tipurilor de caramizi
int m; //numarul de intrebari

long long minim(long long a, long long b)
	{
	if(a<b) return a;
	return b;
	}

void citire(int v[nmax], int *n, int *m)
	{
	int i;
	scanf("%d %d\n",n,m);
	for(i=1;i<=*n;i++) //citim inaltimea fiecarui tip
		scanf("%d",&v[i]);
	}

int divide(int v[nmax], int p, int q)
	{
	int x=v[p];
	while(p<q)
		{
		while(p<q && v[q]>=x) q--; //cel din dreapta e mai mare
		v[p]=v[q]; //il mutam pe cel din dreapta
		while(p<q && v[p]<=x) p++; //cel din stanga e mai mic
		v[q]=v[p]; //il mutam pe cel din stanga in dreapta
		}
	v[p]=x; //punem la pozitia corecta
	return p; //returnam pozitia
	}

void qsort(int v[nmax], int p, int q)
	{
	int m=divide(v,p,q); //plasam pe p corect si ii luam pozitia
	if(m-1>p) qsort(v,q,m-1); //sortam partea stanga
	if(m+1<q) qsort(v,m+1,q); //sortam partea dreapta
	}

void preprocesare(int v[nmax], long long t[nmax], int n)
	{
	int i,j,k;
	for(i=n;i>0;i--) //creeam vectorul t....pe rand
		{
		j=n-i+1; //prima pozitie din grupele ramase
		t[i]=v[j]; //cea mai mica valoare dintre toate tipurile....
		//reimpartim in grupe caramizile
		while(v[j]) //cat timp nu am impartit toate caramizile
			{
			k=j+1;
			while(v[k]==v[k+1]&&k<=n) k++; //cat timp sunt egale
			while(v[j]&&k>j) { v[k--]++; v[j]--; } //mutam unul din grupa ce trebuie eliminata
			}
		}
	}

long long calculeaza(long long t[nmax], int n, int l)
	{
	long long cmax=0,cmax_p; //numarul maxim de caramizi ce se pot folosi construind maxim l turnuri, si cealalta variabila in care calculam in timp ce ne plimbam prin vector
	int i;
	for(i=1;i<=n;i++)
		{
		cmax_p=i*minim(t[i],l);
		if(cmax_p>cmax) cmax=cmax_p;
		}
	return cmax;
	}

int main()
{
int l;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n,&m); //citim
qsort(v,1,n); //sortam lungimile
preprocesare(v,t,n); //preprocesam vectorul t
while(m--) //intrebarile la care trebuie sa raspundem
	{
	scanf("%d",&l); //numarul maxim de turnuri ce pot fi construite
	printf("%lld\n",calculeaza(t,n,l)); //calculam si afisem numarul maxim de caramizi pt numarul maxim de turnuri :P
	}

fclose(stdin);
fclose(stdout);
return 0;
}