結果
問題 | No.1964 sum = length |
ユーザー |
![]() |
提出日時 | 2022-06-03 23:13:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,206 bytes |
コンパイル時間 | 1,753 ms |
コンパイル使用メモリ | 168,152 KB |
実行使用メモリ | 398,080 KB |
最終ジャッジ日時 | 2024-09-21 03:22:05 |
合計ジャッジ時間 | 14,494 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 WA * 4 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)typedef long long ll;bool chmin(ll& a,ll b){if(a>b){a=b; return 1;} return 0;}bool chmax(ll& a,ll b){if(a<b){a=b; return 1;} return 0;}int main(){int n;cin >> n;ll dp[n+2][500][500];rep(i,500){rep(j,500){rep(k,n+2){dp[k][i][j]=0;}}}dp[1][1][1]=1;dp[1][10][1]=-1;dp[1][10][2]=1;dp[1][100][2]=-1;dp[1][100][3]=1;//for(int i=1;i<500;i++){// if(i<10) dp[1][i][1]=1;// else if(i<100) dp[1][i][2]=1;// else dp[1][i][3]=1;//}for(int k=1;k<=n;k++){for(int i=1;i<500;i++){for(int j=1;j<500;j++){dp[k][i][j]+=dp[k][i-1][j];dp[k][i][j]%=998244353;if(i+1>=500 || j+2>=500) break;dp[k+1][i+1][j+2]+=dp[k][i][j];dp[k+1][i+1][j+2]%=998244353;if(i+10>=500 || j+2>=500) break;dp[k+1][i+10][j+2]+=998244353-dp[k][i][j];dp[k+1][i+10][j+2]%=998244353;if(i+10>=500 || j+3>=500) break;dp[k+1][i+10][j+3]+=dp[k][i][j];dp[k+1][i+10][j+3]%=998244353;if(i+100>=500 || j+3>=500) break;dp[k+1][i+100][j+3]+=998244353-dp[k][i][j];dp[k+1][i+100][j+3]%=998244353;if(i+100>=500 || j+4>=500) break;dp[k+1][i+100][j+4]+=dp[k][i][j];dp[k+1][i+100][j+4]%=998244353;//for(int add_a=1;add_a<500;add_a++){// int add_l;// if(add_a<10) add_l=2;// else if(add_a<100) add_l=3;// else add_l=4;//// if(i+add_a>=500 || j+add_l>=500) break;// dp[k+1][i+add_a][j+add_l]+=dp[k][i][j];// dp[k+1][i+add_a][j+add_l]%=998244353;//}}}}ll ans=0;for(int i=1;i<500;i++){ans += dp[n][i][i];ans %=998244353;}cout << ans << endl;return 0;}