Submission #997889
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>; using vvi = vector<vi>;
using vb = vector<bool>; using vvb = vector<vb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;
#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;
// Segment Tree : 時間計算量 O(n log n), 空間計算量 O(n)
// require : なし
// verified :
//
// T はモノイド(単位元を持ち,結合則が成り立つ)であることが要求される
template <class T, class U = size_t>
struct SegTree {
// !!! 実装時 t(lhs, rhs) の引数の順番に注意(意図せず可換則が要求されてしまう) !!!
typedef typename T::V V;
explicit SegTree(U _n = 0, const T &t = T()) : n(1), t(t) {
while (n < _n) n *= 2;
v.assign(n * 2 - 1, t.identity());
if (n >= 2) {
for (U i = n - 2;; --i) {
v[i] = t(v[i * 2 + 1], v[i * 2 + 2]);
if (i == 0) break; // Uが符号無し整数の可能性がある為こう実装している
}
}
}
V operator[](U i) const { return v[n - 1 + i]; }
void set(U i, const V & x) {
i += n - 1;
v[i] = x;
while (i > 0) {
i = (i - 1) / 2;
v[i] = t(v[i * 2 + 1], v[i * 2 + 2]);
}
}
// [a,b)の範囲についてのクエリを返す
V get(U a, U b) const { return q(a, b, 0, 0, n); }
// f(get(0, i), x) == trueを満たす最小のiを返す
// f(get(i, n), x) == trueを満たす最大のiを返す場合はrev:のところを書き換える(未verify).
template<class F>
U lower_bound(const V & x, F && f) const { return lb(x, t.identity(), 0, 0, n, f); }
// f(get(l, i), x) == trueを満たす最小のiを返す
// f(get(i, l), x) == trueを満たす最大のiを返す場合はrev:のところを書き換える(未verify).
// 木をジグザグに登っていったあとlb()で下っていくイメージ
template<class F>
U lower_bound(const V & x, U l, F && f) const {
// rev: l--;
U k = l + n - 1, len = 1;
V nlv = v[k], lv = t.identity();
while (!f(nlv, x)) {
while (k % 2 == 0) { // rev: k % 2 == 1
if (k == 0) return 0; // rev: return n;
k = (k - 1) / 2;
l -= len; // rev: delete
len *= 2;
}
k += 1; // rev: k -= 1;
l += len; // rev: l -= len;
lv = nlv;
nlv = t(nlv, v[k]); // rev: t(v[k], nlv)
}
return lb(x, lv, k, l, l + len, f);
}
private:
// t : traits のインスタンス
// v : 完全二分木の配列表現
// n : 完全二分木の葉の数
T t;
vector<V> v;
U n;
// [a,b)の範囲についてのクエリを返す
// k : 現在見ている接点の番号
// [l,r) : kに対応した範囲
V q(U a, U b, U k, U l, U r) const {
if (r <= a || b <= l) return t.identity(); // 範囲外
if (a <= l && r <= b) return v[k]; // [l,r) ⊂ [a,b)
//[l,r)の一部が[a,b)に含まれる
U c = (l + r) / 2;
return t(
q(a, b, k * 2 + 1, l, c),
q(a, b, k * 2 + 2, c, r)
);
}
template<class F>
U lb(const V & x, const V & lv, U k, U l, U r, F && f) const {
if (k >= n - 1) return f(t(lv, v[k]), x) ? r : 0; // rev: f(t(v[k], lv), x) ? l : n
V nlv = t(lv, v[k * 2 + 1]); // rev: t(v[k * 2 + 2], lv);
U c = (l + r) / 2;
return f(nlv, x) ? lb(x, lv, 2 * k + 1, l, c, f) // rev: lb(x, lv, 2 * k + 2, c, r, f);
: lb(x, nlv, 2 * k + 2, c, r, f); // rev: lb(x, nlv, 2 * k + 1, l, c, f);
}
};
template <class T>
struct LCMTrait {
typedef T V;
V identity() const { return 1; }
V operator()(const V &a, const V &b) const { return lcm(a, b); }
};
template <class T>
struct MinTrait {
typedef T V;
V identity() const { return TEN(10); }
V operator()(const V &a, const V &b) const { return min(a, b); }
};
template <class T>
struct MaxTrait {
typedef T V;
V identity() const { return 0; }
V operator()(const V &a, const V &b) const { return max(a, b); }
};
template <class T>
struct SumTrait {
typedef T V;
V identity() const { return 0; }
V operator()(const V &a, const V &b) const { return a + b; }
};
int main() {
#ifdef INPUT_FROM_FILE
ifstream cin("sample.in");
ofstream cout("sample.out");
#endif
cin.tie(0);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(50);
ll n, m, k; cin >> n >> m >> k;
vl a(n); REP(i, n) cin >> a[i];
SegTree<MaxTrait<ll>> st(n);
REP(i, k) {
for (ll j = n - 1; j >= 0; j--) {
st.set(j, st.get(max<ll>(j - m, 0), j) + a[j] * (i + 1));
}
}
cout << st.get(0, n) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
takamoto |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4836 Byte |
Status |
WA |
Exec Time |
2102 ms |
Memory |
3200 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
subtask3 |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
0 / 200 |
0 / 300 |
0 / 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, 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 |
3 ms |
256 KB |
sample_2.txt |
AC |
3 ms |
256 KB |
sample_3.txt |
AC |
2 ms |
256 KB |
subtask_1_1.txt |
AC |
3 ms |
256 KB |
subtask_1_2.txt |
AC |
329 ms |
640 KB |
subtask_1_3.txt |
TLE |
2102 ms |
3072 KB |
subtask_1_4.txt |
AC |
19 ms |
384 KB |
subtask_1_5.txt |
AC |
81 ms |
3072 KB |
subtask_1_6.txt |
WA |
4 ms |
256 KB |
subtask_1_7.txt |
AC |
1330 ms |
3200 KB |
subtask_1_8.txt |
TLE |
2102 ms |
3072 KB |
subtask_1_9.txt |
WA |
11 ms |
256 KB |
subtask_2_1.txt |
AC |
3 ms |
256 KB |
subtask_2_2.txt |
AC |
3 ms |
256 KB |
subtask_2_3.txt |
AC |
3 ms |
256 KB |
subtask_2_4.txt |
AC |
3 ms |
256 KB |
subtask_2_5.txt |
WA |
3 ms |
256 KB |
subtask_2_6.txt |
WA |
3 ms |
256 KB |
subtask_2_7.txt |
AC |
3 ms |
256 KB |
subtask_2_8.txt |
AC |
3 ms |
256 KB |
subtask_2_9.txt |
AC |
3 ms |
256 KB |
subtask_3_1.txt |
AC |
504 ms |
3072 KB |
subtask_3_2.txt |
AC |
618 ms |
3072 KB |
subtask_3_3.txt |
AC |
601 ms |
3200 KB |
subtask_3_4.txt |
AC |
494 ms |
2944 KB |
subtask_3_5.txt |
AC |
18 ms |
384 KB |
subtask_3_6.txt |
AC |
290 ms |
3072 KB |
subtask_3_7.txt |
AC |
435 ms |
3072 KB |
subtask_3_8.txt |
AC |
53 ms |
640 KB |
subtask_3_9.txt |
AC |
563 ms |
3072 KB |
subtask_4_1.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_10.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_11.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_12.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_13.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_2.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_3.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_4.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_5.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_6.txt |
AC |
318 ms |
3072 KB |
subtask_4_7.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_8.txt |
TLE |
2102 ms |
3072 KB |
subtask_4_9.txt |
TLE |
2102 ms |
3072 KB |