oj.uz

Submission #886029

# Submission time Handle Problem Language Result Execution time Memory
886029 2023-12-11T11:58:55 Z NeroZein Boat (APIO16_boat) C++17
27 / 100
 5 ms 1372 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int md = (int) 1e9 + 7; 
const int N = 503;

int iv[N]; 
int len[N]; 
int dp[N][N]; 
long long a[N], b[N]; 

void add(int& x, int y) {
  x += y;
  if (x >= md) x -= md; 
}

int mul(int x, int y) {
  return (int) ((long long) x * y % md); 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<long long> c; 
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i]; 
    c.push_back(a[i]);
    c.push_back(++b[i]); 
  }
  sort(c.begin(), c.end()); 
  c.resize(unique(c.begin(), c.end()) - c.begin());
  for (int i = 1; i <= n; ++i) {
    a[i] = upper_bound(c.begin(), c.end(), a[i]) - c.begin(); 
    b[i] = upper_bound(c.begin(), c.end(), b[i]) - c.begin(); 
  }
  iv[1] = 1; 
  for (int i = 2; i <= n; ++i) {
    iv[i] = mul(md - md / i, iv[md % i]); 
  }
  int m = (int) c.size(); 
  for (int i = 1; i < m; ++i) {
    len[i] = c[i] - c[i - 1]; 
  }
  for (int i = 0; i <= m; ++i) {
    dp[0][i] = 1; 
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = a[i]; j < b[i]; ++j) {
      int prod = len[j], cnt = 1; 
      for (int k = i - 1; k >= 0; --k) {
        add(dp[i][j], mul(dp[k][j - 1], prod)); 
        if (a[k] <= j && j < b[k]) {
          prod = mul(prod, iv[cnt + 1]); 
          prod = mul(prod, len[j] + cnt);
          cnt++; 
        }
      }
    }
    for (int j = 1; j <= m; ++j) {
      add(dp[i][j], dp[i][j - 1]); 
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    add(ans, dp[i][m]); 
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 5 ms 644 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct

Subtask #4
0 / 42.0

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