Submission #731964

#	Time	Username	Problem	Language	Result	Execution time	Memory
731964		lucri	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	972 ms	293632 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);
    int s=0;
    while(s<n&&p[s]==0)
        ++s;
    for(int i=0;i+s<n;++i)
        p[i]=p[i+s];
    n-=s;
    for(int i=0;i<k&&i<n;++i)
        st[i]=1LL*p[i]*2;
    for(int i=k;i<n;++i)
        st[i]=st[i-k]+1LL*2*p[i];
    for(int i=0;i<k&&i<n;++i)
        dr[n-i-1]=1LL*(l-p[n-i-1])*2;
    for(int i=n-k-1;i>=0;--i)
        dr[i]=dr[i+k]+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:16:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |     for(int i=k;i<n;++i)
      |               ^
boxes.cpp:20:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |     for(int i=n-k-1;i>=0;--i)
      |               ~~~^~

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