Submission #619458

#	Time	Username	Problem	Language	Result	Execution time	Memory
619458		amin	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	622 ms	143148 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
 using namespace std;
 long long n,l,k,ans[2000000];
long long s[2000000];
long long tr(long i)
 {
     if(i==-1)
     {
         return 1e18;
     }
//cout<<i<<endl;
//cout<<i<<endl;
    long long num=n-i*k;
long long f=i*l;
long long j;
//cout<<n<<' '<<i*k<<endl;
j=1e18;
    if(num<=0)
    {

        j=min(j,f);
      return j;
    }
 //   cout<<num<<endl;
// cout<<num<<endl;
 if(s[n-num]>l/2)
 {
   j=min(j,f+ans[n-num]);
 }

    for(long y=0;y<num;y++)
    {

      //  cout<<y<<' '<<i*k+y+1<<endl;
    f=i*l;
        if(s[y]>l/2)
        {
            break;
        }
if(y+i*k+1==n)
{
    j=min(j,f+ans[y]);
    break;
}
//cout<<y<<endl;
if(y+i*k+1>n)
{
    break;
}
        if(s[y+i*k+1]<=l/2)
        {
            continue;
        }
        //cout<<y<<endl;
        f+=ans[y];
        f+=ans[i*k+y+1];
        j=min(j,f);
     //   cout<<y<<' '<<i*k+y+1<<endl;

    }
   // cout<<i<<' '<<j<<endl;

 return j;


}

long long delivery(int N, int K, int L, int p[]) {
   n=N;
   k=K;
    l=L;
   sort(p,p+n);
   for(long i=0;i<n;i++)
   {
       s[i]=p[i];
   }
   long long preo[n];
   long long pree[n];


   long long v=0;

   for(long i=0;i<n;i++)
   {
       if(p[i]>l/2)
        break;


      if(i<k)
      {
          ans[i]=p[i]*2;
          continue;
      }
       ans[i]=ans[i-k]+p[i]*2;


   }
    for(long i=n-1;i>=0;i--)
   {
        if(p[i]<=l/2)
       {
           break;
       }
       long long sum=0;
       if(n-1-i<k)
       {
           ans[i]=(l-p[i])*2;
           continue;
       }

     ans[i]=ans[i+k]+(l-p[i])*2;

   }
  /* for(long i=0;i<n;i++)
   {
       cout<<ans[i]<<endl;
   }*/
   //return v;
   long long h=1e18;
   long long f=0;
   long long i=0;
   long long u=pow(2,25);
   while(u>n/k)
   {
       u/=2;
   }
   long long e=u;
   while(u>=1)
   {
       u/=2;
       if(tr(e-u)>tr(e+u))
       {
           e+=u;
       }else
       {
           e-=u;
       }
   }

return min(tr(e),min(tr(e+1),tr(e-1)));
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:105:18: warning: unused variable 'sum' [-Wunused-variable]
  105 |        long long sum=0;
      |                  ^~~
boxes.cpp:78:14: warning: unused variable 'preo' [-Wunused-variable]
   78 |    long long preo[n];
      |              ^~~~
boxes.cpp:79:14: warning: unused variable 'pree' [-Wunused-variable]
   79 |    long long pree[n];
      |              ^~~~
boxes.cpp:82:14: warning: unused variable 'v' [-Wunused-variable]
   82 |    long long v=0;
      |              ^
boxes.cpp:120:14: warning: unused variable 'h' [-Wunused-variable]
  120 |    long long h=1e18;
      |              ^
boxes.cpp:121:14: warning: unused variable 'f' [-Wunused-variable]
  121 |    long long f=0;
      |              ^
boxes.cpp:122:14: warning: unused variable 'i' [-Wunused-variable]
  122 |    long long i=0;
      |              ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30