Submission #8649654
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); }, 0); seg.build(std::vector<i64>(n + 10, 0)); std::vector<std::vector<i64>> dp( n + 10, std::vector<i64>(k + 10, static_cast<i64>(0))); for(i64 j = 0; j <= k; j++) { if(timer.get() > 1000) assert(0); rep(i, n + 1) seg.update(i, dp[i][j]); 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(i - m, 0LL), i); } } 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 | 3278 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void asaporo_d()’: ./Main.cpp:104:69: error: no matching function for call to ‘max(i64, long long int)’ dp[i][j + 1] = (j + 1) * a[i] + seg.query(max(i - m, 0LL), i); ^ In file included from /usr/include/c++/5/bits/char_traits.h:39:0, from /usr/include/c++/5/ios:40, from /usr/include/c++/5/istream:38, from /usr/include/c++/5/sstream:38, from /usr/include/c++/5/complex:45, from /usr/include/c++/5/ccomplex:38, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52, from ./Main.cpp:1: /usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&) max(const _Tp& __a, const _Tp& __b) ^ /usr/include/c++/5/bits/stl_algobase.h:219:5: note: template argument deduction/substitution failed: ./Main.cpp:104:69: ...