Submission #691758

#	Time	Username	Problem	Language	Result	Execution time	Memory
691758		zeroesandones	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	916 ms	8328 KiB

boxes

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

using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;

#define pb emplace_back

// for i from 1 to K, go till p[l + i] and return and reduce l to l + i + 1
// similarly for r, go till p[r - i] and return and reduce r to r - i - 1

ll memo[1005][1005];

ll calc(int l, int r, int n, int k, int L, int p[]) {
    if(r < l) return 0;
    if(memo[l][r] != -1)
        return memo[l][r];
    ll ans = LLONG_MAX;
    ll sum = 0;
    ll last = 0;
    for(int i = 0; i < k; ++i) {
        if(l + i >= n) break;
        sum += 2 * (p[l + i] - last);
        last = p[l + i];
        ans = min(ans, sum + calc(l + i + 1, r, n, k, L, p));
    }

    sum = 0;
    last = L;
    for(int i = 0; i < k; ++i) {
        if(r - i < 0) break;
        sum += 2 * (last - p[r - i]);
        last = p[r - i];
        ans = min(ans, sum + calc(l, r - i - 1, n, k, L, p));
    }

    return memo[l][r] = ans;
}

ll delivery(int N, int K, int L, int p[]) {
    memset(memo, -1, sizeof(memo));
    ll ans = calc(0, N - 1, N, K, L, p);

    return ans;
}

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