Submission #619436

#	Time	Username	Problem	Language	Result	Execution time	Memory
619436		amin	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2092 ms	19852 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;


       long long sum=0;
       for(long y=i;y>=0;y-=k)
       {
           sum+=p[y];

       }
       ans[i]=sum*2;
       v+=2*p[i];

   }
    for(long i=n-1;i>=0;i--)
   {
        if(p[i]<=l/2)
       {
           break;
       }
       long long sum=0;
     for(long y=i;y<n;y+=k)
     {
         sum+=(l-p[y]);
     }
     ans[i]=sum*2;
     v+=2*(l-p[i]);
   }
   //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: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:114:14: warning: unused variable 'h' [-Wunused-variable]
  114 |    long long h=1e18;
      |              ^
boxes.cpp:115:14: warning: unused variable 'f' [-Wunused-variable]
  115 |    long long f=0;
      |              ^
boxes.cpp:116:14: warning: unused variable 'i' [-Wunused-variable]
  116 |    long long i=0;
      |              ^

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