Submission #8649898
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)
const i64 CYCLES_PER_SEC = 2800000000;
struct Timer {
i64 start;
Timer() { reset(); }
void reset() { start = getCycle(); }
inline double get() {
return (double)(getCycle() - start) / CYCLES_PER_SEC * 1000;
}
private:
inline i64 getCycle() {
uint32_t low, high;
__asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
return ((i64)low) | ((i64)high << 32);
}
} timer;
/* SegmentTree */
template <typename T>
struct SegTree {
using F = function<T(T, T)>;
int n;
F f;
T ti;
vector<T> dat;
SegTree(){};
SegTree(F f, T ti) : f(f), ti(ti) {}
void init(int n_) {
n = 1;
while(n < n_) n <<= 1;
dat.assign(n << 1, ti);
}
void build(const vector<T> &v) {
int n_ = v.size();
init(n_);
for(int i = 0; i < n_; i++) dat[n + i] = v[i];
for(int i = n - 1; i; i--)
dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
}
void update(int k, T x) {
dat[k += n] = x;
while(k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
}
T query(int a, int b) {
T vl = ti, vr = ti;
for(int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
if(l & 1) vl = f(vl, dat[l++]);
if(r & 1) vr = f(dat[--r], vr);
}
return f(vl, vr);
}
template <typename C>
int find(int st, C &check, T &acc, int k, int l, int r) {
if(l + 1 == r) {
acc = f(acc, dat[k]);
return check(acc) ? k - n : -1;
}
int m = (l + r) >> 1;
if(m <= st) return find(st, check, acc, (k << 1) | 1, m, r);
if(st <= l && !check(f(acc, dat[k]))) {
acc = f(acc, dat[k]);
return -1;
}
int vl = find(st, check, acc, (k << 1) | 0, l, m);
if(~vl) return vl;
return find(st, check, acc, (k << 1) | 1, m, r);
}
template <typename C>
int find(int st, C &check) {
T acc = ti;
return find(st, check, acc, 1, 0, n);
}
T operator[](const int &k) const { return dat[k + n]; }
};
// https://atcoder.jp/contests/cf16-tournament-round3-open/tasks/asaporo_d
void asaporo_d() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
std::vector<i64> a(n);
rep(i, n) scanf("%ld", &a[i]);
a.insert(a.begin(), 0LL);
timer.reset();
SegTree<i64> seg([](i64 a, i64 b) { return std::max<i64>(a, b); }, 0LL);
seg.build(std::vector<i64>(n + 1, 0LL));
std::vector<std::vector<i64>> dp(
n + 1, std::vector<i64>(k + 1, static_cast<i64>(0)));
for(i64 j = 0; j < k; j++) {
if(timer.get() > 1000) assert(0);
for(i64 i = 1; i <= n; i++) {
if(j >= i) dp[i][j + 1] = 0;
dp[i][j + 1] = (j + 1) * a[i] + seg.query(max<i64>(i - m, 1), i);
}
rep(i, n + 1) seg.update(i, dp[i][j + 1]);
}
i64 ret = 0;
printf("%ld\n", seg.query(0, n + 1));
}
int main() {
asaporo_d();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
edamat |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3285 Byte |
Status |
RE |
Exec Time |
1139 ms |
Memory |
243440 KB |
Compile Error
./Main.cpp: In function ‘void asaporo_d()’:
./Main.cpp:88:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
^
./Main.cpp:90:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i, n) scanf("%ld", &a[i]);
^
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, 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 |
479 ms |
26496 KB |
subtask_1_3.txt |
RE |
1135 ms |
241392 KB |
subtask_1_4.txt |
AC |
24 ms |
1920 KB |
subtask_1_5.txt |
AC |
105 ms |
11632 KB |
subtask_1_6.txt |
WA |
4 ms |
512 KB |
subtask_1_7.txt |
RE |
1124 ms |
85104 KB |
subtask_1_8.txt |
RE |
1123 ms |
241392 KB |
subtask_1_9.txt |
WA |
15 ms |
1408 KB |
subtask_2_1.txt |
AC |
2 ms |
384 KB |
subtask_2_2.txt |
AC |
1 ms |
256 KB |
subtask_2_3.txt |
AC |
2 ms |
256 KB |
subtask_2_4.txt |
AC |
2 ms |
256 KB |
subtask_2_5.txt |
WA |
1 ms |
256 KB |
subtask_2_6.txt |
WA |
1 ms |
256 KB |
subtask_2_7.txt |
AC |
2 ms |
384 KB |
subtask_2_8.txt |
AC |
2 ms |
384 KB |
subtask_2_9.txt |
AC |
2 ms |
384 KB |
subtask_3_1.txt |
AC |
617 ms |
30448 KB |
subtask_3_2.txt |
AC |
539 ms |
30448 KB |
subtask_3_3.txt |
AC |
549 ms |
30448 KB |
subtask_3_4.txt |
AC |
427 ms |
24844 KB |
subtask_3_5.txt |
AC |
23 ms |
1792 KB |
subtask_3_6.txt |
AC |
183 ms |
19440 KB |
subtask_3_7.txt |
AC |
642 ms |
30448 KB |
subtask_3_8.txt |
AC |
44 ms |
3328 KB |
subtask_3_9.txt |
AC |
492 ms |
30448 KB |
subtask_4_1.txt |
RE |
1136 ms |
241392 KB |
subtask_4_10.txt |
RE |
1129 ms |
241392 KB |
subtask_4_11.txt |
RE |
1126 ms |
241392 KB |
subtask_4_12.txt |
RE |
1130 ms |
241392 KB |
subtask_4_13.txt |
RE |
1126 ms |
241392 KB |
subtask_4_2.txt |
RE |
1131 ms |
241392 KB |
subtask_4_3.txt |
RE |
1122 ms |
243440 KB |
subtask_4_4.txt |
RE |
1136 ms |
241392 KB |
subtask_4_5.txt |
RE |
1139 ms |
205424 KB |
subtask_4_6.txt |
AC |
455 ms |
25712 KB |
subtask_4_7.txt |
RE |
1119 ms |
130416 KB |
subtask_4_8.txt |
RE |
1122 ms |
238332 KB |
subtask_4_9.txt |
RE |
1116 ms |
110064 KB |