結果
問題 | No.616 へんなソート |
ユーザー |
![]() |
提出日時 | 2017-12-18 19:42:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,527 bytes |
コンパイル時間 | 1,873 ms |
コンパイル使用メモリ | 166,196 KB |
実行使用メモリ | 238,080 KB |
最終ジャッジ日時 | 2024-12-16 00:27:07 |
合計ジャッジ時間 | 4,023 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using VI = vector<int>;using VVI = vector<VI>;using PII = pair<int, int>;using LL = long long;using VL = vector<LL>;using VVL = vector<VL>;using PLL = pair<LL, LL>;using VS = vector<string>;#define ALL(a) begin((a)),end((a))#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define EB emplace_back#define MP make_pair#define SZ(a) int((a).size())#define SORT(c) sort(ALL((c)))#define RSORT(c) sort(RALL((c)))#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define FF first#define SS secondtemplate<class S, class T>istream& operator>>(istream& is, pair<S,T>& p){return is >> p.FF >> p.SS;}template<class S, class T>ostream& operator<<(ostream& os, const pair<S,T>& p){return os << p.FF << " " << p.SS;}template<class T>void maxi(T& x, T y){if(x < y) x = y;}template<class T>void mini(T& x, T y){if(x > y) x = y;}const double EPS = 1e-10;const double PI = acos(-1.0);const LL MOD = 1e9+7;const int MAX = 50000;LL dp[301][MAX];LL dpa[301][MAX];int N, K;int main(){cin.tie(0);ios_base::sync_with_stdio(false);cin >> N >> K;dp[0][0] = dpa[0][1] = 1;FOR(i,1,MAX) dpa[0][i] += dpa[0][i-1];for(int l=0;l<N;++l){for(int k=0;k+1<MAX;++k){dp[l+1][k] = (dpa[l][k+1] + MOD - dpa[l][max(0,k-(N-1-l))]) % MOD;dpa[l+1][k+1] = (dpa[l+1][k] + dp[l+1][k]) % MOD;}}cout << dpa[N][K+1] << endl;return 0;}