結果
問題 |
No.616 へんなソート
|
ユーザー |
![]() |
提出日時 | 2017-12-16 01:13:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 727 bytes |
コンパイル時間 | 768 ms |
コンパイル使用メモリ | 75,260 KB |
実行使用メモリ | 54,628 KB |
最終ジャッジ日時 | 2024-12-14 16:45:55 |
合計ジャッジ時間 | 1,754 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; constexpr int P = 1000000007; constexpr int N = 300, K = N * (N - 1) / 2; int dp[N][K + 1]; int main() { int n, k; cin >> n >> k; dp[0][0] = 1; for (int i = 1; i < n; i++) { int k1 = min(k, (i + 1) * i / 2); int64_t t = 0; for (int j = 0; j <= k1; j++) { t += dp[i - 1][j]; if (j - i - 1 >= 0) t -= dp[i - 1][j - i - 1]; dp[i][j] = t % P; } } int64_t r = 0; for (int j = 0; j <= k; j++) { r += dp[n - 1][j]; } r %= P; cout << r << endl; return 0; }