Submission #1012292


Source Code Expand

#include <iostream>
#include <set>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

const int INF = 1 << 30;

int A[100005];
int d[100005][305];

signed main() {
  ios::sync_with_stdio(false);

  int N, M, K;
  cin >> N >> M >> K;

  REP(n, N)
    cin >> A[n+1];

  REP(n, N)
    REP(k, K)
      d[n][k] = -INF;

  d[0][0] = 0;
  FOR(n, 1, N+1)
    d[n][1] = A[n];

  set<int> st;

  FOR(k, 2, K+1) {
    FOR(n, 1, N+1) {
      st.insert(d[n-1][k-1]);
      if(n-M-1 >= 0)
        st.erase(d[n-M-1][k-1]);
      d[n][k] = k * A[n] + (*st.rbegin());
    }
  }

  // for k in range(2,K+1):
  //   for n in range(1,N+1):
  //     d[n, k] = k * A[n] + max(d[n-i, k-1] for i in range(1,M+1))
  //
  // print(max(d[n, K] for n in range(N+1)))
  int result = -INF;
  REP(n, N+1)
    result = max(result, d[n][K]);
  cout << result << endl;

}

Submission Info

Submission Time
Task A - Struck Out
User ukikagi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 933 Byte
Status WA
Exec Time 2116 ms
Memory 248320 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 0 / 200 0 / 300 0 / 100
Status
AC × 2
WA × 1
AC × 1
WA × 5
TLE × 4
AC × 2
WA × 10
AC × 2
WA × 17
TLE × 2
AC × 2
WA × 23
TLE × 18
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, 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 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
sample_3.txt WA 3 ms 256 KB
subtask_1_1.txt WA 3 ms 512 KB
subtask_1_2.txt TLE 2111 ms 151936 KB
subtask_1_3.txt TLE 2116 ms 247936 KB
subtask_1_4.txt WA 64 ms 13440 KB
subtask_1_5.txt WA 297 ms 138496 KB
subtask_1_6.txt WA 14 ms 2304 KB
subtask_1_7.txt TLE 2116 ms 248320 KB
subtask_1_8.txt TLE 2116 ms 247552 KB
subtask_1_9.txt WA 56 ms 7808 KB
subtask_2_1.txt WA 5 ms 896 KB
subtask_2_2.txt WA 3 ms 640 KB
subtask_2_3.txt WA 4 ms 640 KB
subtask_2_4.txt WA 4 ms 768 KB
subtask_2_5.txt WA 3 ms 384 KB
subtask_2_6.txt WA 3 ms 384 KB
subtask_2_7.txt WA 4 ms 640 KB
subtask_2_8.txt WA 5 ms 896 KB
subtask_2_9.txt WA 4 ms 768 KB
subtask_3_1.txt TLE 2113 ms 192768 KB
subtask_3_2.txt WA 1458 ms 123904 KB
subtask_3_3.txt WA 1595 ms 126848 KB
subtask_3_4.txt WA 1156 ms 99840 KB
subtask_3_5.txt WA 61 ms 12928 KB
subtask_3_6.txt WA 415 ms 119936 KB
subtask_3_7.txt TLE 2115 ms 223744 KB
subtask_3_8.txt WA 133 ms 15232 KB
subtask_3_9.txt WA 768 ms 119936 KB
subtask_4_1.txt TLE 2111 ms 156928 KB
subtask_4_10.txt TLE 2109 ms 119808 KB
subtask_4_11.txt TLE 2109 ms 119808 KB
subtask_4_12.txt TLE 2109 ms 119936 KB
subtask_4_13.txt TLE 2109 ms 120064 KB
subtask_4_2.txt TLE 2109 ms 120448 KB
subtask_4_3.txt TLE 2115 ms 223872 KB
subtask_4_4.txt TLE 2110 ms 142848 KB
subtask_4_5.txt TLE 2109 ms 125440 KB
subtask_4_6.txt WA 1873 ms 222848 KB
subtask_4_7.txt TLE 2109 ms 120704 KB
subtask_4_8.txt TLE 2111 ms 154240 KB
subtask_4_9.txt TLE 2109 ms 122624 KB