ログインしてください。
提出 #38739520
ソースコード 拡げる
#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;
void Inc(int &a, const int &b)
{
((a += b) >= MOD) && (a -= MOD);
}
const int N = 305;
char ch[N];
int n, k, m, a[N], sum[N];
int f[2][N][N], ans;
int main()
{
scanf("%s", ch + 1);
scanf("%d", &k);
n = strlen(ch + 1);
ch[++n] = '0';
for(int i = 1, j = 0; i <= n; ++i)
if(ch[i] == '0')
{
a[++m] = i - j - 1;
sum[m] = sum[m - 1] + a[m];
j = i;
}
int now, lst;
now = 0, lst = 1;
f[now][0][0] = 1;
for(int i = 1; i <= m; ++i)
{
now ^= 1, lst = now ^ 1;
memset(f[now], 0, sizeof(f[now]));
for(int j = sum[i - 1]; j <= sum[m]; ++j)
for(int k = 0; k <= sum[m]; ++k)
if(f[lst][j][k])
for(int w = max(sum[i] - j, 0); j + w <= sum[m]; ++w)
Inc(f[now][j + w][k + max(w - a[i], 0)], f[lst][j][k]);
}
for(int i = 0; i <= k && i <= sum[m]; ++i)
Inc(ans, f[now][sum[m]][i]);
printf("%d\n", ans);
return 0;
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | C - Shift |
| ユーザ | Schucking_Sattin |
| 言語 | C++ (GCC 9.2.1) |
| 得点 | 800 |
| コード長 | 1125 Byte |
| 結果 | AC |
| 実行時間 | 51 ms |
| メモリ | 4428 KiB |
コンパイルエラー
./Main.cpp: In function ‘int main()’:
./Main.cpp:14:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
14 | scanf("%s", ch + 1);
| ~~~~~^~~~~~~~~~~~~~
./Main.cpp:15:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
15 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
ジャッジ結果
| セット名 | 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 | 48 ms | 4388 KiB |
| 02.txt | AC | 51 ms | 4260 KiB |
| 03.txt | AC | 45 ms | 4376 KiB |
| 04.txt | AC | 46 ms | 4324 KiB |
| 05.txt | AC | 48 ms | 4324 KiB |
| 06.txt | AC | 40 ms | 4308 KiB |
| 07.txt | AC | 37 ms | 4392 KiB |
| 08.txt | AC | 43 ms | 4376 KiB |
| 09.txt | AC | 11 ms | 4320 KiB |
| 10.txt | AC | 2 ms | 3948 KiB |
| 11.txt | AC | 45 ms | 4396 KiB |
| 12.txt | AC | 46 ms | 4396 KiB |
| 13.txt | AC | 39 ms | 4320 KiB |
| 14.txt | AC | 47 ms | 4368 KiB |
| 15.txt | AC | 49 ms | 4428 KiB |
| 16.txt | AC | 36 ms | 4320 KiB |
| 17.txt | AC | 7 ms | 4320 KiB |
| 18.txt | AC | 44 ms | 4308 KiB |
| 19.txt | AC | 16 ms | 4308 KiB |
| 20.txt | AC | 16 ms | 4260 KiB |
| 21.txt | AC | 6 ms | 4428 KiB |
| 22.txt | AC | 25 ms | 4308 KiB |
| 23.txt | AC | 10 ms | 4428 KiB |
| 24.txt | AC | 8 ms | 4328 KiB |
| 25.txt | AC | 2 ms | 4304 KiB |
| 26.txt | AC | 3 ms | 4392 KiB |
| 27.txt | AC | 11 ms | 4428 KiB |
| 28.txt | AC | 6 ms | 4264 KiB |
| 29.txt | AC | 2 ms | 3972 KiB |
| 30.txt | AC | 2 ms | 4076 KiB |
| 31.txt | AC | 2 ms | 4348 KiB |
| 32.txt | AC | 2 ms | 4364 KiB |
| 33.txt | AC | 2 ms | 4392 KiB |
| 34.txt | AC | 3 ms | 4248 KiB |
| 35.txt | AC | 14 ms | 4428 KiB |
| 36.txt | AC | 2 ms | 4260 KiB |
| s1.txt | AC | 2 ms | 4360 KiB |
| s2.txt | AC | 2 ms | 4324 KiB |
| s3.txt | AC | 3 ms | 4376 KiB |