# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
238974 | ant101 | Boxes with souvenirs (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 "grader.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;
//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007
typedef long long ll;
ll add(ll a, ll b) {
a += b;
if(a >= MOD) {
a -= MOD;
}
return a;
}
ll sub(ll a, ll b) {
a -= b;
if(a < 0) {
a += MOD;
}
return a;
}
ll mul(ll a, ll b) {
return (a * b)%MOD;
}
void add_self(ll& a, ll b) {
a = add(a, b);
}
void sub_self(ll& a, ll b) {
a = sub(a, b);
}
void mul_self(ll& a, ll b) {
a = mul(a, b);
}
const ll MAXN = 200010;
ll li[MAXN], ri[MAXN];
long long delivery(int N, int K, int L, int p[]) {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K >> L;
for (ll i = 0; i<N; i++) {
cin >> p[i];
}
ll zeroteams = 0;
ll currdist = 0, remaining = K;
for (ll i = 0; i<N; i++) {
if (p[i] == 0) {
zeroteams++;
continue;
}
remaining--;
currdist+=p[i]-(i == 0 ? 0 : p[i-1]);
li[i-zeroteams+1] = currdist+p[i];
if (remaining == 0) {
remaining = K;
currdist+=p[i]*2;
}
}
currdist = 0;
remaining = K;
ll curr = 0;
for (ll i = N-1; i>=0; i--) {
if (p[i] == 0) {
continue;
}
remaining--;
curr++;
currdist+=(i == N-1 ? L : p[i+1])-p[i];
ri[curr] = currdist+p[i];
if (remaining == 0) {
remaining = K;
currdist+=(L-p[i])*2;
}
}
N-=zeroteams;
ll best = 1e13;
for (ll i = 0; i<=N; i++) {
best = min(best, li[i]+ri[N-i]);
}
for (ll i = 0; i<=N; i++) {
best = min(best, li[i]+L+ri[N-i-K]);
}
return best;
}