oj.uz

Submission #964584

# Submission time Handle Problem Language Result Execution time Memory
964584 2024-04-17T07:00:55 Z Soumya1 Boat (APIO16_boat) C++17
9 / 100
 1022 ms 11624 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dp[2005][501], ndp[2005][501];
int C[2005][501];
int power(int a, int b) {
  int r = 1;
  while (b > 0) {
    if (b & 1) r = (1LL * r * a) % mod;
    a = (1LL * a * a) % mod, b >>= 1;
  }
  return r;
}
void testCase() {
  int n;
  cin >> n;
  vector<int> l(n + 1), r(n + 1), all;
  for (int i = 1; i <= n; i++) {
    cin >> l[i] >> r[i];
    all.push_back(l[i]);
    all.push_back(r[i]);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  vector<pair<int, int>> ranges;
  vector<int> range_id(all.size());
  for (int i = 0; i < all.size(); i++) {
    if (i > 0 && all[i - 1] + 1 <= all[i] - 1) ranges.push_back({all[i - 1] + 1, all[i] - 1});
    range_id[i] = ranges.size();
    ranges.push_back({all[i], all[i]});
  }
  auto get = [&](int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin();
  };
  int range_cnt = ranges.size();
  for (int i = 0; i < range_cnt; i++) {
    auto [L, R] = ranges[i];
    C[i][0] = 1;
    C[i][1] = R - L + 1;
    for (int j = 2; j <= n; j++) {
      if (j > R - L + 1) C[i][j] = 0;
      else C[i][j] = (1LL * (1LL * C[i][j - 1] * (n - j + 1)) % mod * power(j, mod - 2)) % mod;
    }

  }
  for (int j = 0; j <= range_cnt; j++) dp[j][0] = 1;
  for (int i = 1; i <= n; i++) {
    int L = range_id[get(l[i])], R = range_id[get(r[i])];
    for (int j = L; j <= R; j++) {
      for (int k = 1; k <= n; k++) {
        ndp[j][k] = dp[j][k - 1];
        ndp[j + 1][0] += (1LL * ndp[j][k] * C[j][k]) % mod;
        if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
      }
      ndp[j + 1][0] += ndp[j][0];
      if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
    }
    for (int j = R + 1; j < range_cnt; j++) {
      ndp[j + 1][0] += ndp[j][0];
      if (ndp[j + 1][0] >= mod) ndp[j + 1][0] -= mod;
    }
    for (int j = 0; j <= range_cnt; j++) {
      for (int k = 0; k <= n; k++) {
        dp[j][k] += ndp[j][k];
        if (dp[j][k] >= mod) dp[j][k] -= mod;
        ndp[j][k] = 0;
      }
    }
  }
  int ans = dp[range_cnt][0] - 1;
  if (ans < 0) ans += mod;
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Compilation message

boat.cpp: In function 'void testCase()':
boat.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < all.size(); i++) {
      |                   ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 6224 KB Output is correct
2 Correct 283 ms 6320 KB Output is correct
3 Correct 288 ms 6380 KB Output is correct
4 Correct 304 ms 6644 KB Output is correct
5 Correct 289 ms 6648 KB Output is correct
6 Correct 276 ms 10480 KB Output is correct
7 Correct 284 ms 10208 KB Output is correct
8 Correct 312 ms 6376 KB Output is correct
9 Correct 277 ms 6384 KB Output is correct
10 Correct 281 ms 10476 KB Output is correct
11 Correct 275 ms 6372 KB Output is correct
12 Correct 285 ms 10480 KB Output is correct
13 Correct 288 ms 6376 KB Output is correct
14 Correct 289 ms 6376 KB Output is correct
15 Correct 284 ms 6376 KB Output is correct
16 Correct 51 ms 6820 KB Output is correct
17 Correct 61 ms 1372 KB Output is correct
18 Correct 58 ms 6816 KB Output is correct
19 Correct 53 ms 1372 KB Output is correct
20 Correct 55 ms 1568 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 6224 KB Output is correct
2 Correct 283 ms 6320 KB Output is correct
3 Correct 288 ms 6380 KB Output is correct
4 Correct 304 ms 6644 KB Output is correct
5 Correct 289 ms 6648 KB Output is correct
6 Correct 276 ms 10480 KB Output is correct
7 Correct 284 ms 10208 KB Output is correct
8 Correct 312 ms 6376 KB Output is correct
9 Correct 277 ms 6384 KB Output is correct
10 Correct 281 ms 10476 KB Output is correct
11 Correct 275 ms 6372 KB Output is correct
12 Correct 285 ms 10480 KB Output is correct
13 Correct 288 ms 6376 KB Output is correct
14 Correct 289 ms 6376 KB Output is correct
15 Correct 284 ms 6376 KB Output is correct
16 Correct 51 ms 6820 KB Output is correct
17 Correct 61 ms 1372 KB Output is correct
18 Correct 58 ms 6816 KB Output is correct
19 Correct 53 ms 1372 KB Output is correct
20 Correct 55 ms 1568 KB Output is correct
21 Incorrect 1022 ms 11624 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 6224 KB Output is correct
2 Correct 283 ms 6320 KB Output is correct
3 Correct 288 ms 6380 KB Output is correct
4 Correct 304 ms 6644 KB Output is correct
5 Correct 289 ms 6648 KB Output is correct
6 Correct 276 ms 10480 KB Output is correct
7 Correct 284 ms 10208 KB Output is correct
8 Correct 312 ms 6376 KB Output is correct
9 Correct 277 ms 6384 KB Output is correct
10 Correct 281 ms 10476 KB Output is correct
11 Correct 275 ms 6372 KB Output is correct
12 Correct 285 ms 10480 KB Output is correct
13 Correct 288 ms 6376 KB Output is correct
14 Correct 289 ms 6376 KB Output is correct
15 Correct 284 ms 6376 KB Output is correct
16 Correct 51 ms 6820 KB Output is correct
17 Correct 61 ms 1372 KB Output is correct
18 Correct 58 ms 6816 KB Output is correct
19 Correct 53 ms 1372 KB Output is correct
20 Correct 55 ms 1568 KB Output is correct
21 Incorrect 1022 ms 11624 KB Output isn't correct
22 Halted 0 ms 0 KB -