Submission #1807841
Source Code Expand
#include<bits/stdc++.h> using namespace std; template< typename T > vector< T > slide_min(const vector< T > &v, int k) { deque< int > deq; vector< T > ret; for(int i = 0; i < v.size(); i++) { while(!deq.empty() && v[deq.back()] <= v[i]) { deq.pop_back(); } deq.push_back(i); if(i - k + 1 >= 0) { ret.emplace_back(v[deq.front()]); if(deq.front() == i - k + 1) deq.pop_front(); } } return (ret); } using int64 = long long; int main() { int N, M, K, A[100000]; cin >> N >> M >> K; for(int i = 0; i < N; i++) { cin >> A[i]; } vector< int64 > dp(N); for(int i = 0; i < N; i++) { dp[i] = A[i]; } for(int i = 1; i < K; i++) { vector< int64 > dp2(N); reverse(begin(dp), end(dp)); dp.resize(N + M - 1); reverse(begin(dp), end(dp)); auto p = slide_min(dp, M); for(int j = i; j < N; j++) { dp2[j] = max(dp2[j], p[j - 1] + 1LL * (i + 1) * A[j]); } dp.swap(dp2); } cout << *max_element(begin(dp), end(dp)) << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1086 Byte |
Status | AC |
Exec Time | 908 ms |
Memory | 5112 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 | 77 ms | 800 KB |
subtask_1_3.txt | AC | 904 ms | 5112 KB |
subtask_1_4.txt | AC | 7 ms | 552 KB |
subtask_1_5.txt | AC | 53 ms | 5084 KB |
subtask_1_6.txt | AC | 2 ms | 256 KB |
subtask_1_7.txt | AC | 327 ms | 5112 KB |
subtask_1_8.txt | AC | 908 ms | 5112 KB |
subtask_1_9.txt | AC | 3 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 | 119 ms | 4816 KB |
subtask_3_2.txt | AC | 109 ms | 4352 KB |
subtask_3_3.txt | AC | 107 ms | 4376 KB |
subtask_3_4.txt | AC | 88 ms | 3668 KB |
subtask_3_5.txt | AC | 7 ms | 552 KB |
subtask_3_6.txt | AC | 75 ms | 4324 KB |
subtask_3_7.txt | AC | 123 ms | 5028 KB |
subtask_3_8.txt | AC | 11 ms | 744 KB |
subtask_3_9.txt | AC | 110 ms | 4332 KB |
subtask_4_1.txt | AC | 778 ms | 4552 KB |
subtask_4_10.txt | AC | 403 ms | 4052 KB |
subtask_4_11.txt | AC | 753 ms | 4328 KB |
subtask_4_12.txt | AC | 752 ms | 4328 KB |
subtask_4_13.txt | AC | 746 ms | 4328 KB |
subtask_4_2.txt | AC | 744 ms | 4336 KB |
subtask_4_3.txt | AC | 879 ms | 5024 KB |
subtask_4_4.txt | AC | 766 ms | 4512 KB |
subtask_4_5.txt | AC | 625 ms | 4356 KB |
subtask_4_6.txt | AC | 109 ms | 5112 KB |
subtask_4_7.txt | AC | 409 ms | 4336 KB |
subtask_4_8.txt | AC | 769 ms | 4500 KB |
subtask_4_9.txt | AC | 346 ms | 4344 KB |