Submission #3001637


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

ll A[101010],to[101010],from[101010],deq[101010];

int main(){
  int N,M,K; cin>>N>>M>>K;
  for(int i=1;i<=N;i++){
    cin>>A[i];
    from[i]=A[i];
  }
  for(int i=2;i<=K;i++){
    int s=0,t=0;
    for(int j=1;j<=N;j++){
      while(s<t&&from[deq[t-1]]<=from[j-1]) t--;
      deq[t++]=j-1;
      to[j]=A[j]*i+from[deq[s]];
      if(j-M>=0&&deq[s]==j-M) s++;
    }
    swap(to,from);
  }
  ll ans=0;
  rep(i,N) ans=max(ans,from[i+1]);
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User misosoup
Language C++14 (GCC 5.4.1)
Score 0
Code Size 630 Byte
Status WA
Exec Time 408 ms
Memory 3328 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 × 3
AC × 8
WA × 2
AC × 10
WA × 2
AC × 19
WA × 2
AC × 42
WA × 4
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 2 ms 1792 KB
sample_2.txt AC 2 ms 1792 KB
sample_3.txt AC 2 ms 1792 KB
subtask_1_1.txt AC 5 ms 1792 KB
subtask_1_2.txt AC 69 ms 1920 KB
subtask_1_3.txt AC 406 ms 2560 KB
subtask_1_4.txt AC 9 ms 1920 KB
subtask_1_5.txt AC 45 ms 2560 KB
subtask_1_6.txt WA 24 ms 1792 KB
subtask_1_7.txt AC 162 ms 2560 KB
subtask_1_8.txt AC 407 ms 2560 KB
subtask_1_9.txt WA 35 ms 1792 KB
subtask_2_1.txt AC 5 ms 1792 KB
subtask_2_2.txt AC 3 ms 1792 KB
subtask_2_3.txt AC 4 ms 1792 KB
subtask_2_4.txt AC 5 ms 1792 KB
subtask_2_5.txt WA 5 ms 1792 KB
subtask_2_6.txt WA 5 ms 1792 KB
subtask_2_7.txt AC 5 ms 1792 KB
subtask_2_8.txt AC 5 ms 1792 KB
subtask_2_9.txt AC 4 ms 1792 KB
subtask_3_1.txt AC 76 ms 2560 KB
subtask_3_2.txt AC 77 ms 2560 KB
subtask_3_3.txt AC 74 ms 2560 KB
subtask_3_4.txt AC 62 ms 2432 KB
subtask_3_5.txt AC 9 ms 1920 KB
subtask_3_6.txt AC 57 ms 2560 KB
subtask_3_7.txt AC 76 ms 2560 KB
subtask_3_8.txt AC 12 ms 1920 KB
subtask_3_9.txt AC 76 ms 2560 KB
subtask_4_1.txt AC 405 ms 2560 KB
subtask_4_10.txt AC 163 ms 3328 KB
subtask_4_11.txt AC 387 ms 2688 KB
subtask_4_12.txt AC 398 ms 2688 KB
subtask_4_13.txt AC 408 ms 2688 KB
subtask_4_2.txt AC 403 ms 2560 KB
subtask_4_3.txt AC 407 ms 2560 KB
subtask_4_4.txt AC 406 ms 2560 KB
subtask_4_5.txt AC 348 ms 2560 KB
subtask_4_6.txt AC 67 ms 2560 KB
subtask_4_7.txt AC 231 ms 2560 KB
subtask_4_8.txt AC 401 ms 2560 KB
subtask_4_9.txt AC 201 ms 2560 KB