Submission #619573

#	Time	Username	Problem	Language	Result	Execution time	Memory
619573		someone	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	509 ms	274440 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e7 + 42;

ll dp[N][2], pos[N];

ll delivery(int n, int k, int L, int p[]) {
    k = min(k, n);
    ll len = L;
    for(int i = 0; i < n; i++)
        pos[i] = p[i];

    for(int i = 0; i < k; i++)
        dp[i][0] = pos[i]*2;
    for(int i = k; i < n; i++)
        dp[i][0] = pos[i]*2 + dp[i - k][0];

    for(int i = n-1; i >= n-k; i--)
        dp[i][1] = (len - pos[i]) * 2;
    for(int i = n-k-1; i > -1; i--)
        dp[i][1] = (len - pos[i]) * 2 + dp[i + k][1];

    ll ans = min(dp[n-1][0], dp[0][1]);
    for(int i = 0; i < n-1; i++)
        ans = min(ans, dp[i][0] + dp[i+1][1]);

    ans = min(ans, len + dp[k][1]);
    for(int i = 0; i < n-k; i++)
        ans = min(ans, len + dp[i][0] + dp[i+k+1][1]);
    return ans;
}

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