Submission #1082013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082013		raphael_heuchl	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	2020 ms	332048 KiB

boxes

#include "boxes.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define INF 1'000'000'000'000'000'000

std::vector<long long> people;
long long n, l, k;
long long pos = 0;
long long sum = 0;

long long dist(long long curr, long long next = 0)
{
    long long d = std::abs(people[curr] - people[next]);
    return std::min(d, l - d);
}

long long delivery(int N, int K, int L, int p[])
{
    n = N, k = K, l = L;
    people.push_back(0);
    for (int i = 0; i < N; ++i)
        people.push_back(p[i]);
    std::sort(people.begin(), people.end());
    people.push_back(0);

    int root[N+2]{};
    int next[N+2]{};
    int kDist[N+2]{};

    for (int i = 0; i <= N; ++i)
        root[i] = dist(i),
        next[i] = dist(i, i + 1);
    for (int i = N; i >= 0; --i)
            kDist[i] = kDist[i+1] + next[i] - (i+K-1 <= N+1 ? next[i+K-1] : 0);
    
    long long best = INF;
    for (int i = 1; i <= K; ++i)
    {
        long long sum = 0;
        int pos = 0;
        for (int j = 0; j < i; ++j)
        {
            sum += next[pos];
            ++pos;
        }

        while (pos <= N)
        {
            sum += root[pos];
            sum += root[++pos];
            sum += kDist[pos];
            pos += K-1;
        }

        best = std::min(best, sum);
    }

    return best;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:33:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |         root[i] = dist(i),
      |                   ~~~~^~~
boxes.cpp:34:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |         next[i] = dist(i, i + 1);
      |                   ~~~~^~~~~~~~~~
boxes.cpp:41:19: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   41 |         long long sum = 0;
      |                   ^~~
boxes.cpp:11:11: note: shadowed declaration is here
   11 | long long sum = 0;
      |           ^~~
boxes.cpp:42:13: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   42 |         int pos = 0;
      |             ^~~
boxes.cpp:10:11: note: shadowed declaration is here
   10 | long long pos = 0;
      |           ^~~

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