oj.uz

Submission #849155

# Submission time Handle Problem Language Result Execution time Memory
849155 2023-09-14T07:33:36 Z tch1cherin Boat (APIO16_boat) C++17
27 / 100
 244 ms 524288 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int inverse(int x) {
  int base = x, power = MOD - 2;
  int result = 1;
  while (power > 0) {
    if (power & 1) {
      result = 1LL * result * base % MOD;
    }
    base = 1LL * base * base % MOD;
    power /= 2;
  }
  return result;
}

void norm(int& X) {
  X -= X >= MOD ? MOD : 0;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  vector<int> points;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    points.push_back(A[i]);
    points.push_back(B[i]);
  }
  sort(points.begin(), points.end());
  points.resize(unique(points.begin(), points.end()) - points.begin());
  vector<int> new_points;
  for (int i = 0; i < (int)points.size(); i++) {
    new_points.push_back(points[i]);
    if (i + 1 < (int)points.size() && points[i + 1] - points[i] > 1) {
      new_points.push_back(points[i] + 1);
    } 
  }
  points = new_points;
  int M = (int)points.size();
  vector<int> weight(M);
  vector<vector<int>> choose_weight(M, vector<int>(N + 1));
  for (int i = 0; i < M; i++) {
    weight[i] = (i == M - 1 ? 1 : points[i + 1] - points[i]);
    choose_weight[i][0] = 1;
    for (int j = 0; j < weight[i] && j < N; j++) {
      int coefficient = 1LL * (weight[i] - j) * inverse(j + 1) % MOD;  
      choose_weight[i][j + 1] = 1LL * choose_weight[i][j] * coefficient % MOD;
    }
  }
  vector<int> pref(M + 1);
  vector ways(N + 1, vector(M, vector<int>(N + 1)));
  for (int i = 0; i < M; i++) {
    ways[0][i][0] = 1;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (A[i] <= points[j] && points[j] <= B[i]) {
        ways[i + 1][j][1] += pref[j];
      }
      for (int k = 0; k < N; k++) {
        norm(ways[i + 1][j][k] += ways[i][j][k]);
        if (A[i] <= points[j] && points[j] <= B[i]) {
          norm(ways[i + 1][j][k + 1] += ways[i][j][k]);
        }
      }
    }
    for (int j = 0; j < M; j++) {
      pref[j + 1] = pref[j];
      for (int k = 1; k <= N && k <= weight[j]; k++) {
        pref[j + 1] = (pref[j + 1] + 1LL * ways[i + 1][j][k] * choose_weight[j][k]) % MOD;
      }
    }
  }
  cout << pref[M] << "\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17812 KB Output is correct
2 Correct 25 ms 18072 KB Output is correct
3 Correct 25 ms 18008 KB Output is correct
4 Correct 25 ms 18012 KB Output is correct
5 Correct 25 ms 18012 KB Output is correct
6 Correct 25 ms 18076 KB Output is correct
7 Correct 25 ms 18012 KB Output is correct
8 Correct 28 ms 18012 KB Output is correct
9 Correct 30 ms 18260 KB Output is correct
10 Correct 26 ms 18008 KB Output is correct
11 Correct 24 ms 18012 KB Output is correct
12 Correct 25 ms 18012 KB Output is correct
13 Correct 25 ms 18012 KB Output is correct
14 Correct 26 ms 17952 KB Output is correct
15 Correct 26 ms 18012 KB Output is correct
16 Correct 12 ms 8024 KB Output is correct
17 Correct 11 ms 8224 KB Output is correct
18 Correct 11 ms 8028 KB Output is correct
19 Correct 12 ms 8028 KB Output is correct
20 Correct 11 ms 8212 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -