Submission #1054137
Source Code Expand
#ifndef ___Class_RMQ #define ___Class_RMQ // ------ Includes ------ // #include <limits> #include <vector> #include <algorithm> // ------ RMQ Class ------ // template<typename Type> class RMQ { private: unsigned size_; std::vector<Type> dat; inline Type query_(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return std::numeric_limits<Type>::max(); if (a <= l && r <= b) return dat[k]; Type lc = query_(a, b, (k << 1), l, (l + r) >> 1); Type rc = query_(a, b, (k << 1) + 1, (l + r) >> 1, r); return std::min(lc, rc); } public: RMQ() : size_(0), dat(std::vector<Type>()) {}; RMQ(int size__) { for (size_ = 1; size_ < size__; ) size_ <<= 1; dat.resize(size_ << 1, std::numeric_limits<Type>::max()); } template<class T> RMQ(T begin_, T end_) { int n = end_ - begin_; for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max()); for (int i = 0; i < n; i++) dat[i + size_] = *(begin_ + i); for (int i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]); } inline unsigned size() { return size_; } inline void update(int i, Type x) { i += size_; dat[i] = x; while (i > 1) { i >>= 1; dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]); } } inline Type query(int l, int r) { return query_(l, r, 1, 0, size_); } }; #endif #include <cassert> #include <iostream> using namespace std; long long n, k, m, a[105000], dp[105000][325]; int main() { cin >> n >> m >> k; assert((n*k) < 6000000); for (int i = 0; i < n; i++)cin >> a[i]; vector<RMQ<long long>> x(k + 1, RMQ<long long>(n + 1)); for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++)dp[i][j] = -1LL << 62; } for (int i = 0; i <= n; i++) { dp[i][0] = 0; x[0].update(i, 0); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { dp[i][j] = (-1LL * x[j - 1].query(max(0LL, i - m), i)) + 1LL * j*a[i - 1]; x[j].update(i, -dp[i][j]); } } long long maxn = 0; for (int i = 1; i <= n; i++)maxn = max(maxn, dp[i][k]); cout << maxn << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2115 Byte |
Status | RE |
Exec Time | 953 ms |
Memory | 318588 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 200 / 200 | 300 / 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 | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 512 KB |
subtask_1_2.txt | AC | 584 ms | 103932 KB |
subtask_1_3.txt | RE | 111 ms | 256 KB |
subtask_1_4.txt | AC | 35 ms | 17408 KB |
subtask_1_5.txt | AC | 369 ms | 267260 KB |
subtask_1_6.txt | AC | 6 ms | 1536 KB |
subtask_1_7.txt | RE | 111 ms | 256 KB |
subtask_1_8.txt | RE | 110 ms | 256 KB |
subtask_1_9.txt | AC | 17 ms | 3968 KB |
subtask_2_1.txt | AC | 4 ms | 1280 KB |
subtask_2_2.txt | AC | 4 ms | 1152 KB |
subtask_2_3.txt | AC | 4 ms | 1152 KB |
subtask_2_4.txt | AC | 4 ms | 896 KB |
subtask_2_5.txt | AC | 3 ms | 384 KB |
subtask_2_6.txt | AC | 3 ms | 384 KB |
subtask_2_7.txt | AC | 4 ms | 1280 KB |
subtask_2_8.txt | AC | 4 ms | 1280 KB |
subtask_2_9.txt | AC | 4 ms | 1152 KB |
subtask_3_1.txt | AC | 907 ms | 318588 KB |
subtask_3_2.txt | AC | 953 ms | 318588 KB |
subtask_3_3.txt | AC | 952 ms | 316540 KB |
subtask_3_4.txt | AC | 785 ms | 267644 KB |
subtask_3_5.txt | AC | 37 ms | 17152 KB |
subtask_3_6.txt | AC | 557 ms | 287740 KB |
subtask_3_7.txt | AC | 829 ms | 318588 KB |
subtask_3_8.txt | AC | 85 ms | 33788 KB |
subtask_3_9.txt | AC | 875 ms | 318588 KB |
subtask_4_1.txt | RE | 112 ms | 256 KB |
subtask_4_10.txt | RE | 111 ms | 256 KB |
subtask_4_11.txt | RE | 112 ms | 256 KB |
subtask_4_12.txt | RE | 112 ms | 256 KB |
subtask_4_13.txt | RE | 113 ms | 256 KB |
subtask_4_2.txt | RE | 112 ms | 256 KB |
subtask_4_3.txt | RE | 112 ms | 256 KB |
subtask_4_4.txt | RE | 112 ms | 256 KB |
subtask_4_5.txt | RE | 112 ms | 256 KB |
subtask_4_6.txt | AC | 664 ms | 304124 KB |
subtask_4_7.txt | RE | 112 ms | 256 KB |
subtask_4_8.txt | RE | 112 ms | 256 KB |
subtask_4_9.txt | RE | 112 ms | 256 KB |