Submission #493784

#	Time	Username	Problem	Language	Result	Execution time	Memory
493784		Lam_lai_cuoc_doi	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	549 ms	293964 KiB

boxes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;

constexpr int N = 1e3 + 5;
constexpr ll Inf = 1e17;

long long delivery(int n, int k, int l, int p[])
{
    vector<ll> f(n + 3, Inf), g(n + 3, Inf);
    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        if (i >= k)
            f[i] = f[i - k] + p[i - 1] + min(p[i - 1], l - p[i - 1]);
        else
            f[i] = p[i - 1] + min(p[i - 1], l - p[i - 1]);
    g[n + 1] = 0;
    for (int i = n; i; --i)
        if (n - i + 1 >= k)
            g[i] = g[i + k] + (l - p[i - 1]) + min(p[i - 1], l - p[i - 1]);
        else
            g[i] = (l - p[i - 1]) + min(p[i - 1], l - p[i - 1]);

    ll ans(Inf);

    for (int i = 0; i <= n; ++i)
    {
        ans = min(ans, f[i] + g[i + 1]);
        // cout << i << ":  " << f[i] << " " << g[i + 1] << " " << f[i] + g[i + 1] << "\n";
    }
    return ans;
}

void Read()
{
    int n, l, k;
    cin >> n >> k >> l;
    int a[N];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << delivery(n, k, l, a);
}

void Solve()
{
}

Compilation message (stderr)

boxes.cpp: In function 'void read(T&)':
boxes.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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