Submission #1807811


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,K;
int A[111111];

int dp[111111];

int nex[111111];
signed main(){
    cin>>N>>M>>K;
    rep(i,N)cin>>A[i];
    for(int i=0;i<N;i++)dp[i]=A[i];
    rep(i,K-1){
        deque<int>d;
        for(int j=0;j<N;j++){
            while(d.size()&&j-d.front()>M)d.pop_front();
            if(d.size())nex[j]=(i+2)*A[j]+dp[d.front()];
            else nex[j]=INT_MIN;
            while(d.size()&&dp[d.back()]<=dp[j])d.pop_back();
            d.pb(j);
        }
        rep(j,N)dp[j]=nex[j];
    }

    cout<<*max_element(dp,dp+N)<<endl;
    return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User latte0119
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1021 Byte
Status WA
Exec Time 535 ms
Memory 2560 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 × 11
WA × 1
AC × 20
WA × 1
AC × 43
WA × 3
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 48 ms 512 KB
subtask_1_3.txt AC 493 ms 2560 KB
subtask_1_4.txt AC 5 ms 384 KB
subtask_1_5.txt AC 47 ms 2560 KB
subtask_1_6.txt WA 2 ms 256 KB
subtask_1_7.txt AC 191 ms 2560 KB
subtask_1_8.txt AC 494 ms 2560 KB
subtask_1_9.txt WA 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 WA 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 85 ms 2560 KB
subtask_3_2.txt AC 85 ms 2560 KB
subtask_3_3.txt AC 83 ms 2560 KB
subtask_3_4.txt AC 68 ms 2176 KB
subtask_3_5.txt AC 5 ms 384 KB
subtask_3_6.txt AC 63 ms 2560 KB
subtask_3_7.txt AC 85 ms 2560 KB
subtask_3_8.txt AC 9 ms 512 KB
subtask_3_9.txt AC 88 ms 2560 KB
subtask_4_1.txt AC 494 ms 2560 KB
subtask_4_10.txt AC 438 ms 2560 KB
subtask_4_11.txt AC 535 ms 2560 KB
subtask_4_12.txt AC 532 ms 2560 KB
subtask_4_13.txt AC 529 ms 2560 KB
subtask_4_2.txt AC 520 ms 2560 KB
subtask_4_3.txt AC 494 ms 2560 KB
subtask_4_4.txt AC 495 ms 2560 KB
subtask_4_5.txt AC 423 ms 2560 KB
subtask_4_6.txt AC 74 ms 2560 KB
subtask_4_7.txt AC 291 ms 2560 KB
subtask_4_8.txt AC 486 ms 2560 KB
subtask_4_9.txt AC 248 ms 2560 KB