Submission #731954

#	Time	Username	Problem	Language	Result	Execution time	Memory
731954		lucri	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	340 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
long long st[10000010],dr[10000010];
long long delivery(int N, int K, int L, int p[])
{
    long long n=N,k=K,l=L;
    std::sort(p,p+n);
    st[0]=p[0]*2;
    for(int i=1;i<n;++i)
    {
        if(i%k!=0)
            st[i]=st[i-1]+1LL*2*(p[i]-p[i-1]);
        else
            st[i]=st[i-1]+1LL*2*p[i];
    }
    dr[n-1]=(l-p[n-1])*2;
    for(int i=n-2;i>=0;--i)
    {
        if((i-(n-1))%k!=0)
            dr[i]=dr[i+1]+1LL*2*(p[i+1]-p[i]);
        else
            dr[i]=dr[i+1]+1LL*2*(l-p[i]);
    }
    long long ans=std::min(dr[0],st[n-1]);
    for(int i=0;i<n-1;++i)
        ans=std::min(ans,st[i]+dr[i+1]);
    if(k>=n)
        ans=std::min(ans,l);
    else
    {
        ans=std::min(ans,st[n-k-1]+l);
        ans=std::min(ans,l+st[n-k]);
        for(int i=0;i+k<n-1;++i)
            ans=std::min(ans,st[i]+l+dr[i+k+1]);
    }
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:17:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |     for(int i=n-2;i>=0;--i)
      |               ~^~

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