Educational Codeforces Round 97 F問題 - Emotional Fishermen

Source

Educational Codeforces Round 97 F問題
Problem description

問題概要

省略

解法

省略

cLayversion 20201102-1)のコード

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)

ログイン: