結果

問題 No.3500 01 String
コンテスト
ユーザー MERIDJA ABDELOUAHAB
提出日時 2026-04-17 23:54:45
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,793 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 537 ms
コンパイル使用メモリ 38,784 KB
実行使用メモリ 1,171,328 KB
最終ジャッジ日時 2026-04-17 23:55:05
合計ジャッジ時間 2,995 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 2 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 998244353

int main() {
    int N;
    if (scanf("%d", &N) != 1) return 0;

    char *A = (char *)malloc(N + 1);
    scanf("%s", A);

    // Arrays to store indices of original 0s and 1s
    int *pos0 = (int *)malloc(N * sizeof(int));
    int *pos1 = (int *)malloc(N * sizeof(int));
    int count0 = 0, count1 = 0;

    for (int i = 0; i < N; i++) {
        if (A[i] == '0') {
            pos0[count0++] = i;
        } else {
            pos1[count1++] = i;
        }
    }

    // Allocate 2D DP table: dp[count0 + 1][count1 + 1]
    // Using calloc to initialize all values to 0
    int **dp = (int **)malloc((count0 + 1) * sizeof(int *));
    for (int i = 0; i <= count0; i++) {
        dp[i] = (int *)calloc((count1 + 1), sizeof(int));
    }

    dp[0][0] = 1;

    for (int i = 0; i <= count0; i++) {
        for (int j = 0; j <= count1; j++) {
            if (dp[i][j] == 0) continue;

            int current_idx = i + j;

            // Try to place a '0' next
            // Rule: 0 can move RIGHT (original index <= current target index)
            if (i < count0) {
                if (pos0[i] <= current_idx) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD;
                }
            }

            // Try to place a '1' next
            // Rule: 1 can move LEFT (original index >= current target index)
            if (j < count1) {
                if (pos1[j] >= current_idx) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD;
                }
            }
        }
    }

    printf("%d\n", dp[count0][count1]);

    // Free memory
    for (int i = 0; i <= count0; i++) free(dp[i]);
    free(dp);
    free(pos0);
    free(pos1);
    free(A);

    return 0;
}
0