Submission #668502

#	Time	Username	Problem	Language	Result	Execution time	Memory
668502		victor_gao	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	851 ms	398904 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
 
long long delivery(int N, int K, int L, int p[]) {
    vector<long long>all,dis;
    sort(p,p+N);
    for (int i=0;i<N;i++){
        if (p[i]!=0){
            all.push_back(p[i]);
            dis.push_back(p[i]);
        }
    }
    int n=all.size();
    long long pre[N+5],suf[N+5];
    for (int i=0;i<min(n,K);i++)
        pre[i]=min(2*dis[i],(long long)L);
    for (int i=K;i<n;i++)
        pre[i]=pre[i-K]+min(2*dis[i],(long long)L);
    for (int i=0;i<n;i++)
        dis[i]=L-all[i];
    for (int i=n-1;i>=max(n-K,0);i--)
        suf[i]=min(2*dis[i],(long long)L);
    for (int i=n-1-K;i>=0;i--)
        suf[i]=suf[i+K]+min(2*dis[i],(long long)L);
    long long ans=1e18;
    for (int i=0;i<=n;i++){
        long long tans1=(i-1>=0?pre[i-1]:0);
        long long tans2=(i>=n?0:suf[i]);
        ans=min(ans,tans1+tans2);
    }
    return ans;
}
 

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:14:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   14 |     int n=all.size();
      |           ~~~~~~~~^~

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