Submission #800158

#	Time	Username	Problem	Language	Result	Execution time	Memory
800158		erray	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	502 ms	278380 KiB

boxes

#include "boxes.h"

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi15_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}


long long delivery(int N, int K, int L, int __p[]) {
  vector<int> P = inverse_fuck(__p, N);
  debug(N, K, L, P);
  int mid = 0;
  vector<int> left, right; 
  for (int i = 0; i < N; ++i) {
    if (P[i] == 0) {
      //
    } else if (L % 2 == 0 && P[i] == L / 2) {
      mid += 1;
    } else {
      (P[i] <= L / 2 ? left : right).push_back(P[i]);
    }
  }
  int sl = int(left.size()), sr = int(right.size());
  vector<long long> best_l(sl + 1);
  vector<long long> best_r(sr + 1);
  for (int i = 1; i <= sl; ++i) {
    best_l[i] = best_l[max(0, i - K)] + 2 * left[i - 1];
  }
  for (int i = sr - 1; i >= 0; --i) {
    best_r[i] = best_r[min(sr, i + K)] + 2 * (L - right[i]);
  }
  debug(left, right, best_l, best_r);
  long long ans = 1LL * ((mid + K - 1) / K) * L;
  mid %= K;
  auto Solve = [&](int out) {
    const long long inf = (long long) 1e17;
    long long res = inf;
    for (int i = 0; i <= min(sl, out); ++i) {
      res = min(res, best_l[max(0, sl - i)] + best_r[min(sr, out - i)]);
    }
    debug(out, res);
    return res;
  };
  ans += min({(mid ? Solve(K - mid) : Solve(0)), (mid ? Solve(2 * K - mid) : Solve(K) + L)}); 
  debug(ans);
  return ans;
}

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