結果
問題 | No.1247 ブロック登り |
ユーザー | moririn2528_c |
提出日時 | 2020-10-02 23:01:38 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 572 ms / 3,000 ms |
コード長 | 2,885 bytes |
コンパイル時間 | 933 ms |
コンパイル使用メモリ | 96,004 KB |
実行使用メモリ | 258,936 KB |
最終ジャッジ日時 | 2023-09-24 22:42:12 |
合計ジャッジ時間 | 8,783 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,504 KB |
testcase_01 | AC | 3 ms
9,516 KB |
testcase_02 | AC | 3 ms
11,608 KB |
testcase_03 | AC | 2 ms
5,404 KB |
testcase_04 | AC | 4 ms
13,676 KB |
testcase_05 | AC | 4 ms
13,652 KB |
testcase_06 | AC | 3 ms
5,416 KB |
testcase_07 | AC | 13 ms
48,784 KB |
testcase_08 | AC | 14 ms
53,104 KB |
testcase_09 | AC | 10 ms
42,748 KB |
testcase_10 | AC | 9 ms
34,444 KB |
testcase_11 | AC | 524 ms
257,340 KB |
testcase_12 | AC | 482 ms
247,620 KB |
testcase_13 | AC | 522 ms
258,896 KB |
testcase_14 | AC | 531 ms
258,936 KB |
testcase_15 | AC | 519 ms
258,668 KB |
testcase_16 | AC | 554 ms
258,652 KB |
testcase_17 | AC | 533 ms
258,604 KB |
testcase_18 | AC | 484 ms
246,088 KB |
testcase_19 | AC | 38 ms
46,228 KB |
testcase_20 | AC | 17 ms
21,780 KB |
testcase_21 | AC | 9 ms
7,208 KB |
testcase_22 | AC | 52 ms
191,696 KB |
testcase_23 | AC | 49 ms
190,680 KB |
testcase_24 | AC | 37 ms
182,112 KB |
testcase_25 | AC | 541 ms
258,596 KB |
testcase_26 | AC | 527 ms
258,896 KB |
testcase_27 | AC | 572 ms
258,608 KB |
testcase_28 | AC | 549 ms
258,828 KB |
ソースコード
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<deque> #include<iomanip> #include<tuple> #include<cassert> #include<set> using namespace std; typedef long long int LL; typedef pair<int,int> P; typedef pair<LL,int> LP; const LL INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(LL *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } LL dp[333][333][333]; LL dp2[333][333][2]; LL ans[333]; LL t[333]; int main(){ int n,m; int i,j,k; LL a,b,c; cin>>n>>m; for(i=0;i<=m;i++){ for(j=0;j<n;j++){ for(k=0;k<n;k++){ dp[i][j][k]=-INF; } } } for(i=0;i<n;i++){ for(j=0;j<n;j++){ for(k=0;k<2;k++){ dp2[i][j][k]=-INF; } } } for(i=0;i<n;i++){ ans[i]=-INF; } for(i=0;i<n;i++){ cin>>t[i]; dp[0][i][i]=m*t[i]; } for(i=0;i<m;i++){ for(j=0;j<n;j++){ for(k=0;k<n;k++){ if(dp[i][j][k]==-INF)continue; if(k<=j && j<n-1)dp[i+1][j+1][k]=max(dp[i][j][k]+(m-i-1)*t[j+1],dp[i+1][j+1][k]); if(j<=k && j>0)dp[i+1][j-1][k]=max(dp[i][j][k]+(m-i-1)*t[j-1],dp[i+1][j-1][k]); if(k!=j)dp[i+2][j][k]=max(dp[i][j][k],dp[i+2][j][k]); a=abs(j-k); if(a>0 && i+a<=m)dp[i+a][k][j]=max(dp[i][j][k],dp[i+a][k][j]); if(k<j){ a=max(k,j-(m-i)); if(j-(m-i)<k)b=abs(j-(m-i)-k)%2; else b=0; dp2[a][j][b]=max(dp2[a][j][b],dp[i][j][k]); } if(j<k){ a=min(k,j+(m-i)); b=(m-i)%2; dp2[j][a][b]=max(dp2[j][a][b],dp[i][j][k]); } } } } for(j=0;j<n;j++){ for(k=0;k<n;k++){ ans[j]=max(ans[j],dp[m][j][k]); } } for(i=0;i<n;i++){ for(j=i;j<n;j++){ for(k=0;k<2;k++){ for(a=i+k;a<=j;a+=2){ ans[a]=max(ans[a],dp2[i][j][k]); } } } } for(i=0;i<n;i++){ cout<<ans[i]<<endl; } }