Pagini recente » Cod sursa (job #3137511) | Cod sursa (job #1294215) | Cod sursa (job #2374907) | Cod sursa (job #904896) | Cod sursa (job #253910)
Cod sursa(job #253910)
#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;
}