Submission #1197742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197742		TahirAliyev	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	11 ms	8264 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({2 * arr[r], 2 * (s - arr[l]), s});
    ll ans = oo;
    if(arr[l] == 0) ans = rec(l + 1, r); 
    else ans = min(rec(l + k, r) + min({arr[l + k - 1] * 2, (s - arr[l]) * 2, s}), rec(l, r - k) + min({(s - arr[r - k + 1]) * 2, arr[r] * 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