Submission #1841670
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
import std.typecons;
import std.bigint;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.container.deque;
int main() {
auto sc = new Scanner(stdin);
int n, m, k;
sc.read(n, m, k); m++;
int[] a = new int[n];
a.each!((ref x) => sc.read(x));
long[] dp = a.map!(to!long).array;
long[] ndp = new long[n];
auto deq = Deque!(int, false).make();
foreach (int ph; 2..k+1) {
ndp[] = -(10L^^18);
deq.clear();
foreach (int i; 0..n) {
if (deq.length && deq[0] == i-m) {
deq.removeFront();
}
if (deq.length) {
ndp[i] = dp[deq[0]] + 1L * ph * a[i];
}
while (deq.length && dp[deq.back] <= dp[i]) {
deq.removeBack();
}
deq.insertBack(i);
}
swap(dp, ndp);
}
writeln(dp.fold!max);
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
static if (__VERSION__ <= 2070) {
/*
Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d
Copyright: Andrei Alexandrescu 2008-.
License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
*/
template fold(fun...) if (fun.length >= 1) {
auto fold(R, S...)(R r, S seed) {
import std.algorithm : reduce;
static if (S.length < 2) {
return reduce!fun(seed, r);
} else {
import std.typecons : tuple;
return reduce!fun(tuple(seed), r);
}
}
}
}
T[N] fixed(T, size_t N)(T[N] a) {return a;}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */
// module dcomp.container.deque;
struct DequePayload(T) {
import core.exception : RangeError;
private T* _data;
private uint start, len, cap;
@property bool empty() const { return len == 0; }
@property size_t length() const { return len; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
version(assert) if (len <= i) throw new RangeError();
if (start + i < cap) return _data[start + i];
else return _data[start + i - cap];
}
ref inout(T) front() inout { return this[0]; }
ref inout(T) back() inout { return this[$-1]; }
void reserve(size_t newCap) {
import core.memory : GC;
import std.algorithm : max;
import std.conv : to;
if (newCap <= cap) return;
T* newData = cast(T*)GC.malloc(newCap * T.sizeof);
foreach (i; 0..length) {
newData[i] = this[i];
}
_data = newData; start = 0; cap = newCap.to!uint;
}
void clear() {
start = len = 0;
}
import std.algorithm : max;
void insertFront(T item) {
if (len == cap) reserve(max(cap * 2, 4));
if (start == 0) start += cap;
start--; len++;
this[0] = item;
}
void insertBack(T item) {
if (len == cap) reserve(max(cap * 2, 4));
len++;
this[len-1] = item;
}
void removeFront() {
assert(!empty, "Deque.removeFront: Deque is empty");
start++; len--;
if (start == cap) start = 0;
}
void removeBack() {
assert(!empty, "Deque.removeBack: Deque is empty");
len--;
}
}
struct Deque(T, bool mayNull = true) {
import core.exception : RangeError;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
alias Payload = DequePayload!T;
Payload* _p;
static if (!mayNull) @disable this();
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {
_p = new Payload();
foreach (v; values) {
insertBack(v);
}
}
this(Range)(Range r)
if (isInputRange!Range &&
isImplicitlyConvertible!(ElementType!Range, T) &&
!is(Range == T[])) {
_p = new Payload();
foreach (v; r) {
insertBack(v);
}
}
private this(Payload* p) { _p = p; }
static Deque make() { return Deque(new Payload()); }
private bool havePayload() const { return (!mayNull || _p); }
@property bool empty() const { return (!havePayload || _p.empty); }
@property size_t length() const { return (havePayload ? _p.length : 0); }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
assert(!empty, "Deque.opIndex: Deque is empty");
return (*_p)[i];
}
ref inout(T) front() inout { return this[0]; }
ref inout(T) back() inout { return this[$-1]; }
void clear() { if (_p) _p.clear(); }
void insertFront(T item) {
if (mayNull && !_p) _p = new Payload();
_p.insertFront(item);
}
void insertBack(T item) {
if (mayNull && !_p) _p = new Payload();
_p.insertBack(item);
}
alias opOpAssign(string op : "~") = insertBack;
alias stableInsertBack = insertBack;
void removeFront() {
assert(!mayNull || _p, "Deque.removeFront: Deque is empty");
_p.removeFront();
}
void removeBack() {
assert(!mayNull || _p, "Deque.removeBack: Deque is empty");
_p.removeBack();
}
alias stableRemoveBack = removeBack;
alias Range = RangeT!(DequePayload!T);
alias ConstRange = RangeT!(const DequePayload!T);
alias ImmutableRange = RangeT!(immutable DequePayload!T);
size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const {
assert(start <= end && end <= length);
return [start, end];
}
Range opIndex(size_t[2] rng) { return Range(_p, rng[0], rng[1]); }
ConstRange opIndex(size_t[2] rng) const { return ConstRange(_p, rng[0], rng[1]); }
ImmutableRange opIndex(size_t[2] rng) immutable { return ImmutableRange(_p, rng[0], rng[1]); }
auto opIndex() inout { return this[0..$]; }
static struct RangeT(QualifiedPayload) {
alias A = QualifiedPayload;
import std.traits : CopyTypeQualifiers;
alias E = CopyTypeQualifiers!(A, T);
A *p;
size_t l, r;
@property bool empty() const { return r <= l; }
@property size_t length() const { return r - l; }
alias opDollar = length;
@property auto save() { return this; }
ref inout(E) opIndex(size_t i) inout {
version(assert) if (empty) throw new RangeError();
return (*p)[l+i];
}
@property ref inout(E) front() inout { return this[0]; }
@property ref inout(E) back() inout { return this[$-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
l++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
r--;
}
size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const {
assert(start <= end && end <= length);
return [start, end];
}
auto opIndex(size_t[2] rng) { return RangeT(p, l+rng[0], l+rng[1]); }
auto opIndex(size_t[2] rng) const { return RangeT!(const A)(p, l+rng[0], l+rng[1]); }
auto opIndex(size_t[2] rng) immutable { return RangeT!(immutable A)(p, l+rng[0], l+rng[1]); }
auto opIndex() inout { return this[0..$]; }
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
// import dcomp.container.stackpayload;
class Scanner {
import std.stdio : File;
import std.conv : to;
import std.range : front, popFront, array, ElementType;
import std.array : split;
import std.traits : isSomeChar, isStaticArray, isArray;
import std.algorithm : map;
File f;
this(File f) {
this.f = f;
}
char[512] lineBuf;
char[] line;
private bool succW() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (!line.empty && line.front.isWhite) {
line.popFront;
}
return !line.empty;
}
private bool succ() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (true) {
while (!line.empty && line.front.isWhite) {
line.popFront;
}
if (!line.empty) break;
line = lineBuf[];
f.readln(line);
if (!line.length) return false;
}
return true;
}
private bool readSingle(T)(ref T x) {
import std.algorithm : findSplitBefore;
import std.string : strip;
import std.conv : parse;
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
auto r = line.findSplitBefore(" ");
x = r[0].strip.dup;
line = r[1];
} else static if (isStaticArray!T) {
foreach (i; 0..T.length) {
bool f = succW();
assert(f);
x[i] = line.parse!E;
}
} else {
StackPayload!E buf;
while (succW()) {
buf ~= line.parse!E;
}
x = buf.data;
}
} else {
x = line.parse!T;
}
return true;
}
int read(T, Args...)(ref T x, auto ref Args args) {
if (!readSingle(x)) return 0;
static if (args.length == 0) {
return 1;
} else {
return 1 + read(args);
}
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/stackpayload.d */
// module dcomp.container.stackpayload;
struct StackPayload(T, size_t MINCAP = 4) if (MINCAP >= 1) {
import core.exception : RangeError;
private T* _data;
private uint len, cap;
@property bool empty() const { return len == 0; }
@property size_t length() const { return len; }
alias opDollar = length;
inout(T)[] data() inout { return (_data) ? _data[0..len] : null; }
ref inout(T) opIndex(size_t i) inout {
version(assert) if (len <= i) throw new RangeError();
return _data[i];
}
ref inout(T) front() inout { return this[0]; }
ref inout(T) back() inout { return this[$-1]; }
void reserve(size_t newCap) {
import core.memory : GC;
import core.stdc.string : memcpy;
import std.conv : to;
if (newCap <= cap) return;
void* newData = GC.malloc(newCap * T.sizeof);
cap = newCap.to!uint;
if (len) memcpy(newData, _data, len * T.sizeof);
_data = cast(T*)(newData);
}
void free() {
import core.memory : GC;
GC.free(_data);
}
void clear() {
len = 0;
}
void insertBack(T item) {
import std.algorithm : max;
if (len == cap) reserve(max(cap * 2, MINCAP));
_data[len++] = item;
}
alias opOpAssign(string op : "~") = insertBack;
void removeBack() {
assert(!empty, "StackPayload.removeBack: Stack is empty");
len--;
}
}
/*
This source code generated by dcomp and include dcomp's source code.
dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)
dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)
*/
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
700 |
Code Size |
12147 Byte |
Status |
AC |
Exec Time |
658 ms |
Memory |
4604 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
subtask3 |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
200 / 200 |
300 / 300 |
100 / 100 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 |
sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
subtask3 |
sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
All |
sample_1.txt, sample_2.txt, sample_3.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
64 ms |
636 KB |
subtask_1_3.txt |
AC |
645 ms |
4220 KB |
subtask_1_4.txt |
AC |
5 ms |
508 KB |
subtask_1_5.txt |
AC |
21 ms |
4604 KB |
subtask_1_6.txt |
AC |
2 ms |
256 KB |
subtask_1_7.txt |
AC |
222 ms |
4220 KB |
subtask_1_8.txt |
AC |
645 ms |
3836 KB |
subtask_1_9.txt |
AC |
3 ms |
256 KB |
subtask_2_1.txt |
AC |
1 ms |
256 KB |
subtask_2_2.txt |
AC |
1 ms |
256 KB |
subtask_2_3.txt |
AC |
1 ms |
256 KB |
subtask_2_4.txt |
AC |
1 ms |
256 KB |
subtask_2_5.txt |
AC |
1 ms |
256 KB |
subtask_2_6.txt |
AC |
1 ms |
256 KB |
subtask_2_7.txt |
AC |
1 ms |
256 KB |
subtask_2_8.txt |
AC |
1 ms |
256 KB |
subtask_2_9.txt |
AC |
1 ms |
256 KB |
subtask_3_1.txt |
AC |
74 ms |
3768 KB |
subtask_3_2.txt |
AC |
74 ms |
4604 KB |
subtask_3_3.txt |
AC |
71 ms |
3452 KB |
subtask_3_4.txt |
AC |
59 ms |
4220 KB |
subtask_3_5.txt |
AC |
5 ms |
508 KB |
subtask_3_6.txt |
AC |
42 ms |
3708 KB |
subtask_3_7.txt |
AC |
74 ms |
4280 KB |
subtask_3_8.txt |
AC |
8 ms |
636 KB |
subtask_3_9.txt |
AC |
75 ms |
3708 KB |
subtask_4_1.txt |
AC |
646 ms |
3708 KB |
subtask_4_10.txt |
AC |
530 ms |
4092 KB |
subtask_4_11.txt |
AC |
654 ms |
4604 KB |
subtask_4_12.txt |
AC |
658 ms |
4604 KB |
subtask_4_13.txt |
AC |
658 ms |
4476 KB |
subtask_4_2.txt |
AC |
657 ms |
4152 KB |
subtask_4_3.txt |
AC |
645 ms |
4152 KB |
subtask_4_4.txt |
AC |
646 ms |
4348 KB |
subtask_4_5.txt |
AC |
547 ms |
4024 KB |
subtask_4_6.txt |
AC |
59 ms |
3964 KB |
subtask_4_7.txt |
AC |
350 ms |
4348 KB |
subtask_4_8.txt |
AC |
637 ms |
4604 KB |
subtask_4_9.txt |
AC |
290 ms |
3896 KB |