結果
問題 | No.1238 選抜クラス |
ユーザー |
![]() |
提出日時 | 2020-09-25 22:26:00 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 758 bytes |
コンパイル時間 | 956 ms |
コンパイル使用メモリ | 30,208 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-28 06:50:18 |
合計ジャッジ時間 | 1,996 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<stdio.h> int main() { long long int n, k; scanf("%lld %lld", &n, &k); long long int i, j; long long int a[102]; for (i = 0; i < n; i++) scanf("%lld", &a[i]); for (i = 0; i < n; i++) a[i] -= k; long long int p = 1000000007; long long int dp[20008], m = 10004; for (i = 0; i < 20008; i++) dp[i] = 0; dp[m] = 1; long long int ans = 0; for (i = 0; i < n; i++) { if (a[i] < 0) { for (j = -a[i]; j < 20008; j++) { if (j + a[i] >= m) ans = (ans + dp[j]) % p; dp[j + a[i]] = (dp[j + a[i]] + dp[j]) % p; } } else { for (j = 20007 - a[i]; j >= 0; j--) { if (j + a[i] >= m) ans = (ans + dp[j]) % p; dp[j + a[i]] = (dp[j + a[i]] + dp[j]) % p; } } } printf("%lld\n", ans); return 0; }