Cod sursa(job #63425)

Utilizator crawlerPuni Andrei Paul crawler Data 28 mai 2007 17:19:18
Problema Transport Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <cstdio>
#define pow(q) (1<<(q))

using namespace std;


int v[16100],n;

int nr(int cap)
 {
  int tmp = 0, ret = 0, i;
  for(i=1;i<=n;++i)
   {
    tmp+=v[i];
    if(tmp > cap)
     tmp-=cap, ++ret;
   }
  return ret;
 }

int main()
 {
  freopen("transport.in","r",stdin);
  freopen("transport.out","w",stdout);

  int i,tmp,S,k,t=0;

  scanf("%d%d",&n,&k);

  for(i=1;i<=n;++i)
   scanf("%d",&v[i]);

  for(i=28;i>=0;--i)
   if(t^pow(i) <= n)
    {
     tmp = nr(t^pow(i));
     if(tmp<k)
      tmp^=pow(i);
    }
  ++t;    

  while(t <= n && nr(t) < k) ++t;

  printf("%d\n",t);

  return 0;
 }