結果
問題 |
No.616 へんなソート
|
ユーザー |
![]() |
提出日時 | 2017-12-16 01:15:30 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 738 bytes |
コンパイル時間 | 1,545 ms |
コンパイル使用メモリ | 163,076 KB |
実行使用メモリ | 109,568 KB |
最終ジャッジ日時 | 2024-12-14 16:45:58 |
合計ジャッジ時間 | 2,873 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> #define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++) #define MOD 1000000007LL using namespace std; typedef long long ll; ll N, K, A[300]; int main(void) { cin >> N >> K; REP(i, 0, N) cin >> A[i]; vector< vector<ll> > dp(N + 1, vector<ll>(K + 1, 0)); dp[0][0] = 1; REP(i, 0, N) { vector<ll> sum(K + 2, 0); REP(j, 0, K + 1) sum[j + 1] = dp[i][j]; REP(j, 0, K + 1) { sum[j + 1] += sum[j]; sum[j + 1] %= MOD; } REP(j, 0, K + 1) { ll l = max(j - i, 0LL), r = j; dp[i + 1][j] += (sum[r + 1] - sum[l] + MOD) % MOD; dp[i + 1][j] %= MOD; } } ll ans = 0; REP(i, 0, K + 1) { ans += dp[N][i]; ans %= MOD; } cout << ans << endl; }