結果
問題 | No.1682 Unfair Game |
ユーザー |
👑 |
提出日時 | 2021-08-15 13:09:30 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-29 19:27:49 |
合計ジャッジ時間 | 880 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <stdio.h> const int Mod = 1000000007; int main() { int i, N, P[101]; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%d", &(P[i])); int j, cur, prev, dp[2][101][2] = {}; for (i = 1, cur = 1, prev = 0, dp[0][0][0] = 1; i <= N; i++, cur ^= 1, prev ^= 1) { for (j = 0, dp[cur][0][0] = 0, dp[cur][0][1] = 0; j < i; j++) { dp[cur][j][0] += dp[prev][j][0]; if (dp[cur][j][0] >= Mod) dp[cur][j][0] -= Mod; dp[cur][j][1] += dp[prev][j][1]; if (dp[cur][j][1] >= Mod) dp[cur][j][1] -= Mod; if (P[i] > 50) { dp[cur][j+1][0] = dp[prev][j][1]; dp[cur][j+1][1] = dp[prev][j][0]; } else if (P[i] < 50) { dp[cur][j+1][0] = dp[prev][j][0]; dp[cur][j+1][1] = dp[prev][j][1]; } else { dp[cur][j+1][0] = 0; dp[cur][j+1][1] = 0; } } } long long ans = 0; for (j = 1; j <= N; j++) ans += dp[prev][j][1]; printf("%lld\n", ans % Mod); fflush(stdout); return 0; }