Submission #588384

#	Time	Username	Problem	Language	Result	Execution time	Memory
588384		lorenzoferrari	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	412 ms	8180 KiB

boxes

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

const LL INF = 1e18;

LL solve(int n, int k, int l, vector<int> p) {
  sort(p.begin(), p.end());
  vector<vector<LL>> dp(n+1, vector<LL>(n+1, INF));
  dp[0][0] = 0;
  for (int a = 0; a <= n; ++a) {
    for (int b = 0; a + b <= n; ++b) {
      for (int s = 1; s <= k && s <= a; ++s) {
        dp[a][b] = min(dp[a][b], dp[a - s][b] + p[a - 1]);
      }
      for (int s = 1; s <= k && s <= b; ++s) {
        dp[a][b] = min(dp[a][b], dp[a][b - s] + l - p[n - b]);
      }
    }
  }
  LL ans = INF;
  for (int i = 0; i <= n; ++i) {
    ans = min(ans, dp[i][n - i]);
  }
  return 2 * ans;
}

LL delivery(int n, int k, int l, int p[]) {
  vector<int> v; // those you don't take greedily
  for (int i = 0; i < n; ++i) {
    v.push_back(p[i]);
  }
  return solve(n, k, l, v);
}

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