Submission #390888

#	Time	Username	Problem	Language	Result	Execution time	Memory
390888		usachevd0	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2052 ms	21660 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

const ll inf64 = 1e18;
const int maxN = 10000007;
ll f[maxN];

ll Ceil(ll a, ll b) {
  return a / b + (a % b != 0);
}

ll delivery(int N, int K, int L, int* p) {
  int I = 0;
  while (I < N && p[I] < (L + 1) / 2) ++I;
  for (int i = 0; i < I; ++i) {
    f[i + 1] = f[max(0, i + 1 - K)] + 2 * p[i];
  }
  for (int i = N - 1; i >= I; --i) {
    f[i + 1] = f[min(N + 1, i + 1 + K)] + 2 * (L - p[i]);
  }
  ll ans = L * Ceil(N, K);
  for (int i = -1; i < I; ++i) {
    for (int j = N; j >= I; --j) {
      chkmin(ans, f[i + 1] + f[j + 1] + L * Ceil(j - i - 1, K));
    }
  }
  return ans;
}

#ifdef DEBUG
signed main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K, L;
  cin >> N >> K >> L;
  int* p = new int[N];
  for (int i = 0; i < N; ++i) {
    cin >> p[i];
  }
  cout << delivery(N, K, L, p) << '\n';
    
  return 0;
}
#endif

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