Submission #8658193


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];
  }
  vector<long long> new_dp(n);
  vector<int> st(n);
  for (int it = 1; it < k; it++) {
    new_dp[0] = (long long) -1e18;
    int ptr = 0;
    int end = 0;
    for (int i = 0; i < n - 1; i++) {
      while (ptr < end && st[ptr] <= i - m) {
        ++ptr;
      }
      while (ptr < end && dp[st[end - 1]] <= dp[i]) {
        --end;
      }
      st[end++] = 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 932 Byte
Status AC
Exec Time 353 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
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 31 ms 512 KB
subtask_1_3.txt AC 333 ms 2560 KB
subtask_1_4.txt AC 3 ms 384 KB
subtask_1_5.txt AC 17 ms 2560 KB
subtask_1_6.txt AC 1 ms 256 KB
subtask_1_7.txt AC 119 ms 2560 KB
subtask_1_8.txt AC 335 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 43 ms 2560 KB
subtask_3_2.txt AC 44 ms 2560 KB
subtask_3_3.txt AC 42 ms 2560 KB
subtask_3_4.txt AC 35 ms 2176 KB
subtask_3_5.txt AC 3 ms 384 KB
subtask_3_6.txt AC 27 ms 2560 KB
subtask_3_7.txt AC 43 ms 2560 KB
subtask_3_8.txt AC 5 ms 512 KB
subtask_3_9.txt AC 44 ms 2560 KB
subtask_4_1.txt AC 335 ms 2560 KB
subtask_4_10.txt AC 96 ms 2560 KB
subtask_4_11.txt AC 353 ms 2560 KB
subtask_4_12.txt AC 347 ms 2560 KB
subtask_4_13.txt AC 342 ms 2560 KB
subtask_4_2.txt AC 337 ms 2560 KB
subtask_4_3.txt AC 334 ms 2560 KB
subtask_4_4.txt AC 335 ms 2560 KB
subtask_4_5.txt AC 285 ms 2560 KB
subtask_4_6.txt AC 36 ms 2560 KB
subtask_4_7.txt AC 182 ms 2560 KB
subtask_4_8.txt AC 329 ms 2560 KB
subtask_4_9.txt AC 154 ms 2560 KB