// headers
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// types
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using dbl = double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using piipi = pair<pii, int>;
using pipii = pair<int, pii>;
using plpii = pair<ll, pii>;
using ppii = pair<pii, pii>;
// loops
#define forx(i, x, y) for (int i = (x); i <= (y); ++i)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define for1(i, n) for (int i = 1; i <= (n); ++i)
#define rofx(i, x, y) for (int i = x; i >= y; --i)
#define rofn(i, n) for (int i = n-1; i >= 0; --i)
#define rof1(i, n) for (int i = n; i >= 1; --i)
#define fora(x, v) for (auto x : v)
// define shortcuts
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
// functions
template<class T> inline bool hasbit(T x, int i) { return x&(1<<i); }
template<class T> inline T togbit(T x, int i) { return x|(1<<i); }
template<class T> inline T setbit(T x, int i) { return x|(1<<i); }
template<class T> inline T rembit(T x, int i) { return x&~(1<<i); }
template<class T> inline bool setmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool setmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> int compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v))-v.begin()); return v.size(); }
// read functions
int read_int() { int x; scanf("%d", &x); return x; }
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
void _R(int &x) { x = read_int(); }
void _R(ll &x) { x = read_ll(); }
void _R(dbl &x) { x = read_dbl(); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
// print functions
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%" PRId64, x); }
void _W(const ull &x) { printf("%" PRIu64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
// pseudo-random number generator
template<class T, T x1, T x2, T x3, int y1, int y2, int y3>
struct PRNG {
using S = typename make_signed<T>::type;
T s;
PRNG(T _s = 0) : s(_s) {}
T next() {
T z = (s += x1);
z = (z ^ (z >> y1)) * x2;
z = (z ^ (z >> y2)) * x3;
return z ^ (z >> y3);
}
T next(T n) { return next() % n; }
S next(S l, S r) { return l + next(r - l + 1); }
T operator()() { return next(); }
T operator()(T n) { return next(n); }
S operator()(S l, S r) { return next(l, r); }
static T gen(T s) { return PRNG(s)(); }
template<class U>
void shuffle(U first, U last) {
size_t n = last - first;
for (size_t i = 0; i < n; i++) swap(first[i], first[next(i + 1)]);
}
};
PRNG<uint32_t, 0x9E3779B1, 0x85EBCA6B, 0xC2B2AE35, 16, 13, 16> r32;
PRNG<uint64_t, 0x9E3779B97F4A7C15, 0xBF58476D1CE4E5B9, 0x94D049BB133111EB, 30, 27, 31> r64;
// program
#include "boxes.h"
long long delivery(int n, int k, int l, int p[])
{
setmin(k, n);
ll left[n], right[n];
forn(i, n) left[i] = p[i]*2 + (i-k >= 0 ? left[i-k] : 0);
rofn(i, n) right[i] = (l-p[i])*2 + (i+k < n ? right[i+k] : 0);
int x = lower_bound(p, p+n, (l+1)/2) - p;
//W("found x=", x);
//W("left=", left[x-1], "right=", right[x]);
ll ans = (x-1 >= 0 ? left[x-1] : 0) + (x < n ? right[x] : 0);
forn(i, n) {
ll na = (i-1 >= 0 ? left[i-1] : 0) + (i+k < n ? right[i+k] : 0) + l;
setmin(ans, na);
}
return ans;
}
Compilation message
boxes.cpp: In function 'll read_ll()':
boxes.cpp:49:42: warning: format '%ld' expects argument of type 'long int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
~~^
boxes.cpp: In function 'ull read_ull()':
boxes.cpp:50:45: warning: format '%lu' expects argument of type 'long unsigned int*', but argument 2 has type 'ull* {aka long long unsigned int*}' [-Wformat=]
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
~~^
boxes.cpp: In function 'void _W(const ll&)':
boxes.cpp:60:44: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
void _W(const ll &x) { printf("%" PRId64, x); }
~^
boxes.cpp: In function 'void _W(const ull&)':
boxes.cpp:61:45: warning: format '%lu' expects argument of type 'long unsigned int', but argument 2 has type 'ull {aka long long unsigned int}' [-Wformat=]
void _W(const ull &x) { printf("%" PRIu64, x); }
~^
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:104:42: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
int x = lower_bound(p, p+n, (l+1)/2) - p;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
boxes.cpp: In function 'int read_int()':
boxes.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int read_int() { int x; scanf("%d", &x); return x; }
~~~~~^~~~~~~~~~
boxes.cpp: In function 'll read_ll()':
boxes.cpp:49:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
~~~~~^~~~~~~~~~~~~~~~
boxes.cpp: In function 'ull read_ull()':
boxes.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
~~~~~^~~~~~~~~~~~~~~~
boxes.cpp: In function 'dbl read_dbl()':
boxes.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
256 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
296 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
252 KB |
Output is correct |
30 |
Correct |
2 ms |
256 KB |
Output is correct |
31 |
Correct |
2 ms |
256 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
256 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
296 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
252 KB |
Output is correct |
30 |
Correct |
2 ms |
256 KB |
Output is correct |
31 |
Correct |
2 ms |
256 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
53 ms |
19832 KB |
Output is correct |
34 |
Correct |
27 ms |
19836 KB |
Output is correct |
35 |
Correct |
29 ms |
19876 KB |
Output is correct |
36 |
Correct |
52 ms |
19996 KB |
Output is correct |
37 |
Correct |
60 ms |
19832 KB |
Output is correct |
38 |
Correct |
51 ms |
19832 KB |
Output is correct |
39 |
Correct |
46 ms |
19916 KB |
Output is correct |
40 |
Correct |
32 ms |
19912 KB |
Output is correct |
41 |
Correct |
50 ms |
19880 KB |
Output is correct |
42 |
Correct |
34 ms |
19872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
256 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
296 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
252 KB |
Output is correct |
30 |
Correct |
2 ms |
256 KB |
Output is correct |
31 |
Correct |
2 ms |
256 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
53 ms |
19832 KB |
Output is correct |
34 |
Correct |
27 ms |
19836 KB |
Output is correct |
35 |
Correct |
29 ms |
19876 KB |
Output is correct |
36 |
Correct |
52 ms |
19996 KB |
Output is correct |
37 |
Correct |
60 ms |
19832 KB |
Output is correct |
38 |
Correct |
51 ms |
19832 KB |
Output is correct |
39 |
Correct |
46 ms |
19916 KB |
Output is correct |
40 |
Correct |
32 ms |
19912 KB |
Output is correct |
41 |
Correct |
50 ms |
19880 KB |
Output is correct |
42 |
Correct |
34 ms |
19872 KB |
Output is correct |
43 |
Correct |
504 ms |
195944 KB |
Output is correct |
44 |
Correct |
282 ms |
195960 KB |
Output is correct |
45 |
Correct |
292 ms |
196048 KB |
Output is correct |
46 |
Correct |
500 ms |
195936 KB |
Output is correct |
47 |
Correct |
510 ms |
195960 KB |
Output is correct |
48 |
Correct |
489 ms |
196064 KB |
Output is correct |
49 |
Correct |
461 ms |
195992 KB |
Output is correct |
50 |
Correct |
303 ms |
196000 KB |
Output is correct |
51 |
Correct |
492 ms |
195976 KB |
Output is correct |
52 |
Correct |
312 ms |
195972 KB |
Output is correct |