初投稿です

競プロやっているomochanという人です。適当に解いた問題を載せていくのでよろしくお願いします。

JOI Kangaroo

int N;
ll dp[2][MAX_N][MAX_N];
pi P[MAX_N];
int C[MAX_N];
bool bigger(const pi& p1, const pi& p2) {
 return p1.second < p2.second;
}
void solve() {
 cin >> N;
 rep(i, 0, N) {
  int a, b;
  cin >> a >> b;
  P[i] = make_pair(a, b);
 }
 sort(P, P + N, bigger);
 rep(i, 0, N) {
  int c1 = 0, c2 = 0;
  int a1 = (i == 0 ? 0 : P[i - 1].sec), a2 = P[i].sec;
  rep(j, 0, i) {
   if(P[j].fst < a2) c2++;
   if(P[j].fst < a1) c1++;
  }
  C[i] = c2 - c1;
 }
 dp[0][0][0] = 1;
 int pre, nex;
 rep(i, 0, N) {
  pre = i % 2; nex = 1 - i % 2;
  rep(j, 0, N + 1) 
   rep(k, 0, N + 1) dp[nex][j][k] = 0;
  rep(j, 0, N) {
   rep(k, 0, N) {
    if(k - C[i] >= 0) {
     ADD(dp[nex][j][k], dp[pre][j + 1][k - C[i]] * (j + 1));
    }
    if(k - C[i] + 1 >= 0) {
     ADD(dp[nex][j][k], dp[pre][j][k - C[i] + 1] * (k + 1));
    }
   }
   rep(k, 0, j - C[i] + 1) {
    ADD(dp[nex][j][0], dp[pre][j - C[i] - k][k]);
   }
  }
 }
 ll res = 0;
 rep(i, 0, N) ADD(res, dp[nex][0][i]);
 cout << res << '\n';
}