Cod sursa(job #253909)

Utilizator FlorianFlorian Marcu Florian Data 6 februarie 2009 13:35:02
Problema Caramizi Scor 5
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 1.15 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 200002
using namespace std;
FILE*f=fopen("caramizi.in","r");
FILE*g=fopen("caramizi.out","w");
int nr[Nmax]; // nr[h] - nr turnuri de inaltime h
int a[Nmax]; // a[i] - nr de caramizi de tip i
int n,m; //nr de tipuri
void NR()
 {
  sort(a+1,a+n+1);
  int b[Nmax];
  int h,i,k,j,min=0,x;
  for(h=1;h<=n;++h)
   {
    // calculez nr max de turnuri de inaltime h
    for(i=1;i<=n;++i) b[i] = a[i];
    k=n;
    while(k>=h)   //cat timp am mai mult de h elemente
     {
      nr[h] += b[n-h+1];
      x=b[n-h+1];
      for(i=n-h+1;i<=n;++i)
       b[i]-=x;
      sort(b+1,b+n+1);
      --k;
     }
    for(i=1;i<=n;++i) nr[h] += b[i]/h;
    }
 }

int Q(int x) // nr max de caramizi pt a construi cel mult x turnuri
  {
   int m=0;
   int h;
   for(h=n;h>=1;--h)

    if(x>nr[h])

     { if(m < h*nr[h]) m=h*nr[h];}

    else

     if(m < x*h) m=x*h;

   return m;
  }
int main()
 {
  fscanf(f,"%d%d",&n,&m);
  int i,x;
  for(i=1;i<=n;++i) fscanf(f,"%d",&a[i]);
  NR();
  while(m--)
   {
    fscanf(f,"%d",&x);
    fprintf(g,"%d\n",Q(x));
   }
  return 0;
  }