Educational Codeforces Round 97 F問題
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
#define MD 998244353
int N, A[5000], can[5001], nx[5001];
Comb<Modint> c;
Modint dp[5001][5001], ad[5001][5001];
{
rd(N,A(N));
sortA(N,A);
can[0] = -1;
rep(i,N) rep(j,i) if(2*A[j] <= A[i]) can[i+1]++;
rep(i,N+1){
rep(k,i,N) if(can[k+1] >= i) nx[i] = k+1, break_continue;
nx[i] = -1;
}
dp[0][0] = 1;
rep(i,N+1) rep(j,N+1) if(dp[i][j] || ad[i][j]){
dp[i][j] += ad[i][j];
if(i+1 <= N) ad[i+1][j] += ad[i][j];
if(can[i] >= j) dp[i][j+1] += dp[i][j] * (can[i] - j + 1);
if(nx[i] != -1) ad[nx[i]][j+1] += dp[i][j];
}
wt(dp[N][N]);
}
Current time: 2024年03月29日21時59分20秒
Last modified: 2020年11月03日21時50分44秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る
Logged in as: unknown user (not login)