Submission #8658136


Source Code Expand

/**
 *    author:  tourist
 *    created: 26.11.2019 09:39:34       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<long long> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = a[i];
  }
  for (int it = 1; it < k; it++) {
    vector<long long> new_dp(n);
    new_dp[0] = (long long) -1e18;
    vector<int> st;
    int ptr = 0;
    for (int i = 0; i < n - 1; i++) {
      while (ptr < (int) st.size() && st[ptr] <= i - m) {
        ++ptr;
      }
      while (ptr < (int) st.size() && dp[st.back()] <= dp[i]) {
        st.pop_back();
      }
      st.push_back(i);
      new_dp[i + 1] = dp[st[ptr]] + (it + 1LL) * a[i + 1];
    }
    swap(dp, new_dp);
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User tourist
Language C++14 (GCC 5.4.1)
Score 700
Code Size 947 Byte
Status AC
Exec Time 413 ms
Memory 3184 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 100 / 100 200 / 200 300 / 300 100 / 100
Status
AC × 3
AC × 10
AC × 12
AC × 21
AC × 46
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 39 ms 512 KB
subtask_1_3.txt AC 406 ms 2272 KB
subtask_1_4.txt AC 4 ms 384 KB
subtask_1_5.txt AC 18 ms 2272 KB
subtask_1_6.txt AC 1 ms 256 KB
subtask_1_7.txt AC 143 ms 2272 KB
subtask_1_8.txt AC 406 ms 2272 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 50 ms 2272 KB
subtask_3_2.txt AC 51 ms 2272 KB
subtask_3_3.txt AC 49 ms 2272 KB
subtask_3_4.txt AC 41 ms 1816 KB
subtask_3_5.txt AC 3 ms 384 KB
subtask_3_6.txt AC 31 ms 2288 KB
subtask_3_7.txt AC 50 ms 2272 KB
subtask_3_8.txt AC 6 ms 512 KB
subtask_3_9.txt AC 51 ms 2288 KB
subtask_4_1.txt AC 408 ms 2272 KB
subtask_4_10.txt AC 215 ms 3184 KB
subtask_4_11.txt AC 411 ms 2304 KB
subtask_4_12.txt AC 413 ms 2304 KB
subtask_4_13.txt AC 410 ms 2288 KB
subtask_4_2.txt AC 407 ms 2288 KB
subtask_4_3.txt AC 406 ms 2272 KB
subtask_4_4.txt AC 407 ms 2272 KB
subtask_4_5.txt AC 345 ms 2272 KB
subtask_4_6.txt AC 41 ms 2272 KB
subtask_4_7.txt AC 220 ms 2288 KB
subtask_4_8.txt AC 400 ms 2176 KB
subtask_4_9.txt AC 185 ms 2272 KB