Submission #798430

#	Time	Username	Problem	Language	Result	Execution time	Memory
798430		qthang2k11	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	464 ms	293844 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e7 + 5;

ll pref[N], suff[N];
int *p;

ll delivery(int n, int k, int m, int _p[]) { // n <= m, duoc dua toi da k
  if (m == 1) return 0;
  // if (n == 1) return min({m - 1, p[0] * 2, });
  p = _p;
  for (int i = 0; i < n; i++) {
    pref[i] = (i - k >= 0 ? pref[i - k] : 0) + 2LL * p[i];
  }
  for (int i = n - 1; i >= 0; i--) {
    suff[i] = (i + k < n ? suff[i + k] : 0) + 2LL * (m - p[i]);
  }
  ll ans = min(1LL * m * n, suff[0]);
  for (int i = 0; i < n; i++) {
    ans = min(ans, pref[i] + suff[i + 1]);
    ll cur = 0;
    if (i - 1 >= 0) cur += pref[i - 1];
    if (i + k < n) cur += suff[i + k];
    cur += m;
    ans = min(ans, cur);
  }
  return ans;
}

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