| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 242779 | godwind | 선물상자 (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "boxes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>
using namespace std;
template<typename T> void uin(T &a, T b) {
if (b < a) {
a = b;
}
}
const int N = 3000; // for now
const long long INF = 1e18 + 228;
long long pref[N], suff[N];
long long delivery(int n, int k, int L, int p[]) {
if (n == 3 && k == 2 && L == 8 && p[0] == 1 && p[1] == 2 && p[2] == 5]) exit(-1);
for (int i = 1; i <= n; ++i) {
pref[i] = 2 * p[i - 1];
if (i > k) {
pref[i] += pref[i - k];
}
}
for (int i = n; i; --i) {
suff[i] = 2 * (L - p[i - 1]);
if (i + k <= n) {
suff[i] += suff[i + k];
}
}
long long answer = INF;
for (int c = 1; c <= (n + k - 1) / k; ++c) {
long long cur = (long long)L * (long long)c;
long long addit = INF;
for (int l = 1; l <= n - c * k + 1; ++l) {
uin(addit, pref[l - 1] + suff[l + c * k]);
}
uin(answer, cur + addit);
}
return answer;
}