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
AC × 3
AC × 5
WA × 2
RE × 3
AC × 10
WA × 2
AC × 19
WA × 2
AC × 27
WA × 4
RE × 15
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