Submission #3447763
Source Code Expand
#include <deque> #include <iostream> using namespace std; using ll = long long; int main() { ll N, M, K; cin >> N >> M >> K; ll A[N + 1]; for (ll i = 1; i <= N; ++i) { cin >> A[i]; } ll dp[N + 1]; fill(dp, dp + N + 1, 0); // dp[n] = A_nをk個目として選んだときの最大スコア // kについて逐次更新 for (ll k = 1; k <= K; ++k) { ll ndp[N + 1]; deque<ll> que; // スライド最大値 // [i - M + 1, i]の最大値を求める for (ll i = 0; i < N; ++i) { // 古い上に値の小さいindexを破棄 while (!que.empty() && dp[que.back()] <= dp[i]) { que.pop_back(); } que.push_back(i); // 先頭が範囲内か確認 while (que.front() <= i - M) { que.pop_front(); } ndp[i + 1] = dp[que.front()] + A[i + 1] * k; } // k未満を更新するとWA // A_1がやたら大きいときにA_1 * Kを答えにしてしまう for (ll i = k; i <= N; ++i) { dp[i] = ndp[i]; } } ll ans = 0; for (ll i = 1; i <= N; ++i) { ans = max(ans, dp[i]); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | Tiramister |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1354 Byte |
Status | AC |
Exec Time | 465 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 | 426 ms | 2560 KB |
subtask_1_4.txt | AC | 5 ms | 384 KB |
subtask_1_5.txt | AC | 46 ms | 2560 KB |
subtask_1_6.txt | AC | 2 ms | 256 KB |
subtask_1_7.txt | AC | 170 ms | 2560 KB |
subtask_1_8.txt | AC | 428 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 | 79 ms | 2560 KB |
subtask_3_2.txt | AC | 78 ms | 2560 KB |
subtask_3_3.txt | AC | 77 ms | 2560 KB |
subtask_3_4.txt | AC | 63 ms | 2176 KB |
subtask_3_5.txt | AC | 5 ms | 384 KB |
subtask_3_6.txt | AC | 60 ms | 2560 KB |
subtask_3_7.txt | AC | 79 ms | 2560 KB |
subtask_3_8.txt | AC | 9 ms | 512 KB |
subtask_3_9.txt | AC | 82 ms | 2560 KB |
subtask_4_1.txt | AC | 427 ms | 2560 KB |
subtask_4_10.txt | AC | 365 ms | 2560 KB |
subtask_4_11.txt | AC | 465 ms | 2560 KB |
subtask_4_12.txt | AC | 461 ms | 2560 KB |
subtask_4_13.txt | AC | 458 ms | 2560 KB |
subtask_4_2.txt | AC | 450 ms | 2560 KB |
subtask_4_3.txt | AC | 428 ms | 2560 KB |
subtask_4_4.txt | AC | 429 ms | 2560 KB |
subtask_4_5.txt | AC | 366 ms | 2560 KB |
subtask_4_6.txt | AC | 70 ms | 2560 KB |
subtask_4_7.txt | AC | 255 ms | 2560 KB |
subtask_4_8.txt | AC | 422 ms | 2560 KB |
subtask_4_9.txt | AC | 211 ms | 2560 KB |