Submission #8650103

---

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 <class T>
class SegTree {
    using F = function<T(T, T)>;
    int n;
    vector<T> data;
    F f;
    T e;

   public:
    SegTree<T>() {}
    SegTree<T>& operator=(const SegTree<T>& t) {
        n = t.n;
        data = t.data;
        f = t.f;
        e = t.e;
        return *this;
    }
    SegTree<T>(const vector<T>& as, const F f, const T& e) : f(f), e(e) {
        n = 1;
        while(n < as.size()) n <<= 1;
        data.assign(2 * n, e);
        for(int i = 0; i < as.size(); i++) {
            data[n + i] = as[i];
        }
        for(int i = n - 1; i > 0; i--) {
            data[i] = f(data[2 * i], data[2 * i + 1]);
        }
    }

    void update(int k, const T& x) {
        k += n;
        data[k] = x;
        while(k >>= 1) {
            data[k] = f(data[2 * k], data[2 * k + 1]);
        }
    }

    T query(int a, int b) {
        assert(a >= 0 and b <= n);
        T L = e, R = e;
        for(a += n, b += n; a < b; a >>= 1, b >>= 1) {
            if(a & 1) {
                L = f(L, data[a++]);
            }
            if(b & 1) {
                R = f(data[--b], R);
            }
        }
        return f(L, R);
    }

    T operator[](const int& k) const { return data[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(std::vector<i64>(n + 1, 0),
                     [](i64 a, i64 b) { return std::max<i64>(a, b); }, -1e18);

    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, 0), i);
        }
        rep(i, n + 1) seg.update(i, dp[i][j + 1]);
        // rep(i, n + 1) printf("%ld ", seg[i]);
        // printf("\n");
    }
    i64 ret = 0;
    printf("%ld\n", seg.query(0, n + 1));
}

int main() {
    asaporo_d();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void asaporo_d()’:
./Main.cpp:85: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:87: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