Submission #1913686
Source Code Expand
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<unordered_map> #include<array> #include<map> #include<bitset> #include<iomanip> #include<list> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define RE return 0 //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=1e9+7; const int big=1e9+100; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} template <class T> void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}} llint lcm(llint a,llint b){return a/gcd(a,b) *b;} int main(void){ //(部分点はRMQ) //スライド最大値₯ //O(NK) llint n,m,K,i,j,ans=0;cin>>n>>m>>K; vector<llint>dp(n); vector<llint>pot(n); for(i=0;i<n;i++){cin>>pot[i];} for(i=1;i<=K;i++){ deque<pair<int,llint>>slide; if(i==1){slide.pub(mp(0,0LL));} for(j=0;j<n;j++){ llint mot=dp[j]; if(slide.size()>0&&slide.front().fir<j-m){slide.pof();} if(i-1<=j){ dp[j]=slide.front().sec+i*pot[j]; maxeq(ans,dp[j]); } while(slide.size()>0&&slide.back().sec<=mot){slide.pob();} slide.pub(mp(j,mot)); //cerr<<dp[j]<<" "; } //cerr<<endl; } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1969 Byte |
Status | AC |
Exec Time | 567 ms |
Memory | 1920 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, 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 | 49 ms | 384 KB |
subtask_1_3.txt | AC | 497 ms | 1792 KB |
subtask_1_4.txt | AC | 6 ms | 384 KB |
subtask_1_5.txt | AC | 48 ms | 1792 KB |
subtask_1_6.txt | AC | 2 ms | 256 KB |
subtask_1_7.txt | AC | 193 ms | 1792 KB |
subtask_1_8.txt | AC | 496 ms | 1792 KB |
subtask_1_9.txt | AC | 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 | AC | 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 | 86 ms | 1792 KB |
subtask_3_2.txt | AC | 87 ms | 1792 KB |
subtask_3_3.txt | AC | 84 ms | 1792 KB |
subtask_3_4.txt | AC | 70 ms | 1536 KB |
subtask_3_5.txt | AC | 5 ms | 384 KB |
subtask_3_6.txt | AC | 66 ms | 1792 KB |
subtask_3_7.txt | AC | 86 ms | 1792 KB |
subtask_3_8.txt | AC | 10 ms | 384 KB |
subtask_3_9.txt | AC | 92 ms | 1920 KB |
subtask_4_1.txt | AC | 498 ms | 1792 KB |
subtask_4_10.txt | AC | 466 ms | 1792 KB |
subtask_4_11.txt | AC | 566 ms | 1792 KB |
subtask_4_12.txt | AC | 567 ms | 1792 KB |
subtask_4_13.txt | AC | 558 ms | 1792 KB |
subtask_4_2.txt | AC | 552 ms | 1792 KB |
subtask_4_3.txt | AC | 498 ms | 1792 KB |
subtask_4_4.txt | AC | 498 ms | 1792 KB |
subtask_4_5.txt | AC | 433 ms | 1792 KB |
subtask_4_6.txt | AC | 75 ms | 1792 KB |
subtask_4_7.txt | AC | 309 ms | 1792 KB |
subtask_4_8.txt | AC | 492 ms | 1792 KB |
subtask_4_9.txt | AC | 259 ms | 1792 KB |