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 |
|
|
|
|
|
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 |