Submission #3630389
Source Code Expand
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; struct SlideMin { // data[i]: mininum over [max(0, i + 1 - width), i + 1) int n; vi data; SlideMin(const vi &as, int width, bool minimum = true) : n(as.size()), data(as.size()) { using ii = pair<i64, int>; deque<ii> deq; auto comp = [&](ii &e, i64 v) { return minimum ? e.first >= v : e.first <= v; }; for (int i = 0; i < n; i++) { if (deq.size() && deq.front().second <= i - width) { deq.pop_front(); } while (deq.size()) { if (comp(deq.back(), as[i])) deq.pop_back(); else break; } deq.push_back(ii(as[i], i)); data[i] = deq.front().first; } } }; 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); for (int i = 0; i < k - 1; i++) { SlideMin smax(dp, m, false); for (int j = 0; j < n; j++) { if (j <= i) { dp[j] = 0; } else { dp[j] = smax.data[j - 1] + as[j] * (i + 2); } } } 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 | 1541 Byte |
Status | AC |
Exec Time | 513 ms |
Memory | 2672 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 | 512 KB |
subtask_1_3.txt | AC | 454 ms | 2672 KB |
subtask_1_4.txt | AC | 4 ms | 384 KB |
subtask_1_5.txt | AC | 18 ms | 2672 KB |
subtask_1_6.txt | AC | 2 ms | 256 KB |
subtask_1_7.txt | AC | 159 ms | 2672 KB |
subtask_1_8.txt | AC | 454 ms | 2672 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 | 2672 KB |
subtask_3_2.txt | AC | 56 ms | 2672 KB |
subtask_3_3.txt | AC | 54 ms | 2672 KB |
subtask_3_4.txt | AC | 46 ms | 2188 KB |
subtask_3_5.txt | AC | 4 ms | 384 KB |
subtask_3_6.txt | AC | 36 ms | 2672 KB |
subtask_3_7.txt | AC | 55 ms | 2672 KB |
subtask_3_8.txt | AC | 7 ms | 512 KB |
subtask_3_9.txt | AC | 60 ms | 2672 KB |
subtask_4_1.txt | AC | 454 ms | 2672 KB |
subtask_4_10.txt | AC | 250 ms | 2672 KB |
subtask_4_11.txt | AC | 513 ms | 2672 KB |
subtask_4_12.txt | AC | 513 ms | 2672 KB |
subtask_4_13.txt | AC | 507 ms | 2672 KB |
subtask_4_2.txt | AC | 499 ms | 2672 KB |
subtask_4_3.txt | AC | 453 ms | 2672 KB |
subtask_4_4.txt | AC | 454 ms | 2672 KB |
subtask_4_5.txt | AC | 394 ms | 2672 KB |
subtask_4_6.txt | AC | 45 ms | 2672 KB |
subtask_4_7.txt | AC | 269 ms | 2672 KB |
subtask_4_8.txt | AC | 460 ms | 2560 KB |
subtask_4_9.txt | AC | 219 ms | 2672 KB |