Submission #404933

#	Time	Username	Problem	Language	Result	Execution time	Memory
404933		EJOI2019Andrew	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	550 ms	252712 KiB

boxes

#include "boxes.h"

  #include<bits/stdc++.h>
using namespace std;
long long mn(int a,int b)
{
     if(a<b)
return a;

 return b;
}
  long long int dp[10000009],dp1[10000009];

long long delivery(int N, int K,int L, int p[]) {

    if(K==N)
    {

        sort(p, p+N);
        int mid = L/2;
        int sum = 0;
        for(int i = 0; i < N; i++)
            {
            if(p[i] <= mid)
            {

                sum = p[i]*2;
            }
            else if(p[i] > mid)
                {
                sum+=((L-p[i])*2);
            break;
            }
        }
        return min(sum, L);
    }
  else if(K==1)
    {
       long long ans = 0;
        for(int i = 0; i < N; ++i)
            ans+=mn(p[i],L-p[i])*2;
        return ans;
    }

    else
    {

      int n=N,k=K;
       int l=L;
     for(int i=0;i<n;i++)
        {
		if(i<k)
			dp[i] = min(p[i]*2,l);
		else
			dp[i] = dp[i-k]+min(p[i]*2,l);
	}
	for(int i=n-1;i>=0;i--)
        {
		if(i>=n-k)
			dp1[i] = min((l-p[i])*2,l);
		else{
			dp1[i] = dp1[i+k] +min((l-p[i])*2,l);
		}
	}
	long long int ans = dp1[0];
	for(int i=0;i<n;i++)
		ans = min(ans,dp[i]+dp1[i+1]);
    return ans;

    }
}

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