Submission #889048

#	Time	Username	Problem	Language	Result	Execution time	Memory
889048		TahirAliyev	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	5 ms	8412 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 1005;

ll dp[MAX][MAX];
int arr[MAX];
int n, k, s;

ll rec(int l, int r){
    if(dp[l][r] != -1) return dp[l][r];
    if(r - l + 1 <= k){
        return min(min(2 * arr[r], 2 * (s - arr[l])), s);
    }
    ll ans = rec(l + k, r) + min(arr[l + k - 1] * 2, s);
    ans = min(ans, rec(l, r - k) + min((s - arr[r - k + 1]) * 2, s));
    return dp[l][r] = ans;
}

ll delivery(int N, int K, int L, int p[]) {
    n = N;
    k = K;
    s = L;
    for(int i = 1; i <= n; i++){
        arr[i] = p[i - 1];
    }
    memset(dp, -1, sizeof(dp));
    return rec(1, n);
}

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