結果
問題 |
No.616 へんなソート
|
ユーザー |
![]() |
提出日時 | 2017-12-29 12:42:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 1,095 ms |
コンパイル使用メモリ | 83,512 KB |
実行使用メモリ | 39,856 KB |
最終ジャッジ日時 | 2024-12-21 10:28:03 |
合計ジャッジ時間 | 1,789 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <string> #include <climits> #include <functional> #include "math.h" using namespace std; typedef long long ll; int main() { int N, K; string A; cin >> N >> K; cin >> A; if (N == 1) { cout << 1 << endl; } else { vector<vector<ll> > cum(N + 1, vector<ll>()); cum[1].push_back(0); cum[1].push_back(1); cum[1].push_back(1); int j_max = 2; for (int i = 2; i <= N; ++i) { ll sum_val = 0; cum[i].push_back(0); for (int j = 0; j < min(j_max, K + 1); ++j) { sum_val += (cum[i - 1][j + 1] - cum[i - 1][max(0, j - i + 1)]) % 1000000007; cum[i].push_back(sum_val % 1000000007); } j_max += i; for (int j = 0; j < i; ++j) { cum[i].push_back(sum_val % 1000000007); } } cout << cum[N][K + 1] % 1000000007 << endl; } }