ログインしてください。
提出 #17598887
ソースコード 拡げる
#include<bits/stdc++.h>
using namespace std;
int const p=998244353;
int f[305][305][305],s[305][305][305],a[305],s2[305][305][305];
char str[305];
int mod(int x){return x>=p?x-p:x;}
int main()
{
int n,m,cnt=1,sum=0;
scanf("%s\n%d",str+1,&m);
n=strlen(str+1);
str[n+1]='0';
for(int i=1;i<=n;i++)
if(str[i]=='1')a[cnt]++,sum++;
else cnt++;
f[0][0][0]=1;
m=min(m,sum);
for(int i=0;i<=sum;i++)s[0][i][0]=1,s2[0][0][i]=1;
for(int i=1,now=a[1];i<=cnt;i++,now+=a[i])
for(int j=now;j<=sum;j++)
for(int k=0;k<=m;k++)
{
f[i][j][k]=mod(s[i-1][j][k]-(j==a[i]?0:s[i-1][j-a[i]-1][k])+p);
if(j-a[i]-k>=0)f[i][j][k]=mod(f[i][j][k]+s2[i-1][j-a[i]-k][k-1]);
s[i][j][k]=mod(s[i][j-1][k]+f[i][j][k]);
if(j>=k)s2[i][j-k][k]=mod((k?s2[i][j-k][k-1]:0)+f[i][j][k]);
}
int res=0;
for(int i=0;i<=m;i++)res=mod(res+f[cnt][sum][i]);
printf("%d",res);
return 0;
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | C - Shift |
| ユーザ | AzusaCat |
| 言語 | C++ (GCC 9.2.1) |
| 得点 | 800 |
| コード長 | 1041 Byte |
| 結果 | AC |
| 実行時間 | 58 ms |
| メモリ | 84504 KiB |
コンパイルエラー
./Main.cpp: In function ‘int main()’:
./Main.cpp:10:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
10 | scanf("%s\n%d",str+1,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 800 / 800 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | s1.txt, s2.txt, s3.txt |
| All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| 01.txt | AC | 50 ms | 57900 KiB |
| 02.txt | AC | 45 ms | 56912 KiB |
| 03.txt | AC | 49 ms | 57236 KiB |
| 04.txt | AC | 39 ms | 51612 KiB |
| 05.txt | AC | 45 ms | 55708 KiB |
| 06.txt | AC | 40 ms | 49108 KiB |
| 07.txt | AC | 44 ms | 55924 KiB |
| 08.txt | AC | 50 ms | 60964 KiB |
| 09.txt | AC | 7 ms | 7232 KiB |
| 10.txt | AC | 3 ms | 4016 KiB |
| 11.txt | AC | 45 ms | 58472 KiB |
| 12.txt | AC | 49 ms | 59024 KiB |
| 13.txt | AC | 52 ms | 58088 KiB |
| 14.txt | AC | 46 ms | 54528 KiB |
| 15.txt | AC | 45 ms | 48464 KiB |
| 16.txt | AC | 40 ms | 56988 KiB |
| 17.txt | AC | 8 ms | 8332 KiB |
| 18.txt | AC | 48 ms | 57228 KiB |
| 19.txt | AC | 10 ms | 9448 KiB |
| 20.txt | AC | 15 ms | 9824 KiB |
| 21.txt | AC | 11 ms | 7124 KiB |
| 22.txt | AC | 15 ms | 12336 KiB |
| 23.txt | AC | 20 ms | 23524 KiB |
| 24.txt | AC | 21 ms | 23128 KiB |
| 25.txt | AC | 6 ms | 5644 KiB |
| 26.txt | AC | 3 ms | 5012 KiB |
| 27.txt | AC | 58 ms | 84504 KiB |
| 28.txt | AC | 31 ms | 26148 KiB |
| 29.txt | AC | 3 ms | 3604 KiB |
| 30.txt | AC | 2 ms | 3780 KiB |
| 31.txt | AC | 2 ms | 3788 KiB |
| 32.txt | AC | 2 ms | 3868 KiB |
| 33.txt | AC | 2 ms | 4264 KiB |
| 34.txt | AC | 7 ms | 6072 KiB |
| 35.txt | AC | 9 ms | 9884 KiB |
| 36.txt | AC | 2 ms | 3852 KiB |
| s1.txt | AC | 2 ms | 3788 KiB |
| s2.txt | AC | 2 ms | 3712 KiB |
| s3.txt | AC | 4 ms | 6304 KiB |