Submission #997930
Source Code Expand
#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<map> #include<queue> #include<cassert> #define PB push_back #define MP make_pair #define sz(v) (in((v).size())) #define forn(i,n) for(in i=0;i<(n);++i) #define forv(i,v) forn(i,sz(v)) #define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i) #define all(v) (v).begin(),(v).end() using namespace std; typedef long long in; typedef vector<in> VI; typedef vector<VI> VVI; VI stk; in lf,rt; void clr(){ stk.clear(); lf=0; rt=0; } void ad(in a){ while(rt>lf && stk[rt-1]<a) --rt; if(rt==sz(stk)) stk.PB(0); stk[rt]=a; ++rt; } void rm(in a){ if(lf<rt && stk[lf]==a) ++lf; } in bst(){ if(lf==rt) return -1; return stk[lf]; } VI a; VI bs[2]; int main(){ ios::sync_with_stdio(0); cin.tie(0); in n,m,k; cin>>n>>m>>k; a.resize(n); forn(i,n) cin>>a[i]; forn(z,2) bs[z].resize(n); in sw=1; in nw=0; bs[nw]=a; forn(i,n) bs[nw][i]*=k; for(in z=1;z<k;++z){ swap(nw,sw); clr(); for(in i=n-1;i>=0;--i){ bs[nw][i]=bst(); if(bs[nw][i]!=-1) bs[nw][i]+=(k-z)*a[i]; ad(bs[sw][i]); if(i+m<n) rm(bs[sw][i+m]); } } in r=0; forn(i,n) r=max(r,bs[nw][i]); cout<<r<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | w4yneb0t |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1339 Byte |
Status | AC |
Exec Time | 530 ms |
Memory | 3196 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 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, 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 | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 40 ms | 512 KB |
subtask_1_3.txt | AC | 477 ms | 2560 KB |
subtask_1_4.txt | AC | 5 ms | 384 KB |
subtask_1_5.txt | AC | 22 ms | 2560 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 169 ms | 2560 KB |
subtask_1_8.txt | AC | 478 ms | 2688 KB |
subtask_1_9.txt | AC | 4 ms | 256 KB |
subtask_2_1.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 3 ms | 256 KB |
subtask_2_3.txt | AC | 3 ms | 256 KB |
subtask_2_4.txt | AC | 3 ms | 256 KB |
subtask_2_5.txt | AC | 3 ms | 256 KB |
subtask_2_6.txt | AC | 3 ms | 256 KB |
subtask_2_7.txt | AC | 3 ms | 256 KB |
subtask_2_8.txt | AC | 3 ms | 256 KB |
subtask_2_9.txt | AC | 3 ms | 256 KB |
subtask_3_1.txt | AC | 62 ms | 2688 KB |
subtask_3_2.txt | AC | 63 ms | 2560 KB |
subtask_3_3.txt | AC | 61 ms | 2560 KB |
subtask_3_4.txt | AC | 50 ms | 2176 KB |
subtask_3_5.txt | AC | 5 ms | 384 KB |
subtask_3_6.txt | AC | 39 ms | 2688 KB |
subtask_3_7.txt | AC | 61 ms | 2560 KB |
subtask_3_8.txt | AC | 8 ms | 512 KB |
subtask_3_9.txt | AC | 63 ms | 2688 KB |
subtask_4_1.txt | AC | 497 ms | 2560 KB |
subtask_4_10.txt | AC | 425 ms | 3196 KB |
subtask_4_11.txt | AC | 530 ms | 2944 KB |
subtask_4_12.txt | AC | 520 ms | 2816 KB |
subtask_4_13.txt | AC | 509 ms | 2688 KB |
subtask_4_2.txt | AC | 501 ms | 2688 KB |
subtask_4_3.txt | AC | 482 ms | 2560 KB |
subtask_4_4.txt | AC | 498 ms | 2560 KB |
subtask_4_5.txt | AC | 424 ms | 2560 KB |
subtask_4_6.txt | AC | 50 ms | 2560 KB |
subtask_4_7.txt | AC | 271 ms | 2688 KB |
subtask_4_8.txt | AC | 499 ms | 2560 KB |
subtask_4_9.txt | AC | 228 ms | 2560 KB |