Submission #3630309
Source Code Expand
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m, k; cin >> n >> m >> k; vi as(n); for (int i = 0; i < n; i++) { cin >> as[i]; } vi dp(as); using ii = pair<i64, int>; for (int i = 0; i < k - 1; i++) { deque<ii> deq; vi dp2(n); for (int j = 0; j < n; j++) { // for (int d = 0; d < deq.size(); d++) { // cout << "DEBUG " << deq[d].first << " " << deq[d].second << endl; // } if (j >= i + 1) { dp2[j] = (i + 2) * as[j] + deq.front().first; } if (deq.size() && deq.front().second <= j - m) { deq.pop_front(); } while (deq.size()) { if (deq.back().first <= dp[j]) deq.pop_back(); else break; } deq.push_back(ii(dp[j], j)); } dp = vi(dp2); } i64 nax = -1; for (int i = 0; i < n; i++) { nax = max(nax, dp[i]); } cout << nax << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | xuzijian629 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1242 Byte |
Status | AC |
Exec Time | 525 ms |
Memory | 4236 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 | 45 ms | 640 KB |
subtask_1_3.txt | AC | 446 ms | 3456 KB |
subtask_1_4.txt | AC | 4 ms | 512 KB |
subtask_1_5.txt | AC | 19 ms | 3456 KB |
subtask_1_6.txt | AC | 2 ms | 256 KB |
subtask_1_7.txt | AC | 156 ms | 3456 KB |
subtask_1_8.txt | AC | 447 ms | 3456 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 | 55 ms | 3456 KB |
subtask_3_2.txt | AC | 56 ms | 3456 KB |
subtask_3_3.txt | AC | 54 ms | 3456 KB |
subtask_3_4.txt | AC | 46 ms | 2816 KB |
subtask_3_5.txt | AC | 4 ms | 512 KB |
subtask_3_6.txt | AC | 37 ms | 4176 KB |
subtask_3_7.txt | AC | 55 ms | 3456 KB |
subtask_3_8.txt | AC | 7 ms | 640 KB |
subtask_3_9.txt | AC | 61 ms | 3456 KB |
subtask_4_1.txt | AC | 446 ms | 3456 KB |
subtask_4_10.txt | AC | 257 ms | 3456 KB |
subtask_4_11.txt | AC | 525 ms | 4236 KB |
subtask_4_12.txt | AC | 520 ms | 4220 KB |
subtask_4_13.txt | AC | 512 ms | 4220 KB |
subtask_4_2.txt | AC | 499 ms | 4176 KB |
subtask_4_3.txt | AC | 446 ms | 3456 KB |
subtask_4_4.txt | AC | 446 ms | 3456 KB |
subtask_4_5.txt | AC | 383 ms | 3456 KB |
subtask_4_6.txt | AC | 45 ms | 3456 KB |
subtask_4_7.txt | AC | 270 ms | 3456 KB |
subtask_4_8.txt | AC | 440 ms | 3328 KB |
subtask_4_9.txt | AC | 221 ms | 4176 KB |