Submission #424387

#	Time	Username	Problem	Language	Result	Execution time	Memory
424387		SuhaibSawalha1	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	50 ms	21676 KiB

boxes

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

const int N = 1000;
long long dp[N][N];
int a[N], n, l, k;

int f (int i, int j) {
	return min({l, 2 * a[j], 2 * (l - a[i])});
}

long long calc (int i = 0, int s = 0) {
	if (i == n) {
		return s ? f(i - s, i - 1) : 0;
	}
	long long &ret = dp[i][s];
	if (~ret) {
		return ret;
	}
	ret = calc(i + 1, 0) + f(i - s, i);
	if (s + 1 != k) {
		ret = min(ret, calc(i + 1, s + 1));
	}
	return ret;
}

long long delivery(int N, int K, int L, int p[]) {
	n = N;
	l = L;
	k = K;
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < N; ++i) {
		a[i] = p[i];
	}
	return calc();
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:28:24: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   28 | long long delivery(int N, int K, int L, int p[]) {
      |                    ~~~~^
boxes.cpp:5:11: note: shadowed declaration is here
    5 | const int N = 1000;
      |           ^

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