Submission #3139657
Source Code Expand
#include <bits/stdc++.h> using namespace std; using lint = long long int; template<class T = int> using V = vector<T>; template<class T = int> using VV = V< V<T> >; template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); } template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); } int main() { cin.tie(NULL); ios::sync_with_stdio(false); int n, m, k; cin >> n >> m >> k; V<lint> a(n); for (int i = 0; i < n; i++) cin >> a[i]; VV<lint> dp; assign(dp, 2, n + 1); for (int i = 1; i < k + 1; i++) { deque<int> dq; for (int j = max(i - m, 0); j < i; j++) { while(!dq.empty() and dp[i - 1 & 1][dq.back()] <= dp[i - 1 & 1][j]) dq.pop_back(); dq.push_back(j); } for (int j = i; j < n + 1; j++) { dp[i & 1][j] = i * a[j - 1] + dp[i - 1 & 1][dq.front()]; if (dq.front() == j - m) dq.pop_front(); while (!dq.empty() and dp[i - 1 & 1][dq.back()] <= dp[i - 1 & 1][j]) dq.pop_back(); dq.push_back(j); } } cout << *max_element(dp[k & 1].begin(), dp[k & 1].end()) << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | risujiroh |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1150 Byte |
Status | AC |
Exec Time | 501 ms |
Memory | 2560 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 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 | 42 ms | 512 KB |
subtask_1_3.txt | AC | 473 ms | 2560 KB |
subtask_1_4.txt | AC | 4 ms | 384 KB |
subtask_1_5.txt | AC | 18 ms | 2560 KB |
subtask_1_6.txt | AC | 1 ms | 256 KB |
subtask_1_7.txt | AC | 165 ms | 2560 KB |
subtask_1_8.txt | AC | 474 ms | 2560 KB |
subtask_1_9.txt | AC | 2 ms | 256 KB |
subtask_2_1.txt | AC | 1 ms | 256 KB |
subtask_2_2.txt | AC | 1 ms | 256 KB |
subtask_2_3.txt | AC | 1 ms | 256 KB |
subtask_2_4.txt | AC | 1 ms | 256 KB |
subtask_2_5.txt | AC | 1 ms | 256 KB |
subtask_2_6.txt | AC | 1 ms | 256 KB |
subtask_2_7.txt | AC | 1 ms | 256 KB |
subtask_2_8.txt | AC | 1 ms | 256 KB |
subtask_2_9.txt | AC | 1 ms | 256 KB |
subtask_3_1.txt | AC | 57 ms | 2560 KB |
subtask_3_2.txt | AC | 57 ms | 2560 KB |
subtask_3_3.txt | AC | 55 ms | 2560 KB |
subtask_3_4.txt | AC | 46 ms | 2176 KB |
subtask_3_5.txt | AC | 4 ms | 384 KB |
subtask_3_6.txt | AC | 35 ms | 2560 KB |
subtask_3_7.txt | AC | 57 ms | 2560 KB |
subtask_3_8.txt | AC | 6 ms | 512 KB |
subtask_3_9.txt | AC | 59 ms | 2560 KB |
subtask_4_1.txt | AC | 475 ms | 2560 KB |
subtask_4_10.txt | AC | 143 ms | 2560 KB |
subtask_4_11.txt | AC | 499 ms | 2560 KB |
subtask_4_12.txt | AC | 501 ms | 2560 KB |
subtask_4_13.txt | AC | 496 ms | 2560 KB |
subtask_4_2.txt | AC | 486 ms | 2560 KB |
subtask_4_3.txt | AC | 474 ms | 2560 KB |
subtask_4_4.txt | AC | 475 ms | 2560 KB |
subtask_4_5.txt | AC | 402 ms | 2560 KB |
subtask_4_6.txt | AC | 46 ms | 2560 KB |
subtask_4_7.txt | AC | 260 ms | 2560 KB |
subtask_4_8.txt | AC | 467 ms | 2560 KB |
subtask_4_9.txt | AC | 215 ms | 2560 KB |