Submission #849153

#	Time	Username	Problem	Language	Result	Execution time	Memory
849153		tch1cherin	Boat (APIO16_boat)	C++17	58 / 100	2041 ms	12576 KiB

boat

#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<vector<int>> ways(M, vector<int>(N + 1));
  vector<int> pref(M + 1);
  for (int i = 0; i < M; i++) {
    ways[i][0] = 1;
  }
  for (int i = 0; i < N; i++) {
    vector<vector<int>> new_ways(M, vector<int>(N + 1));
    for (int j = 0; j < M; j++) {
      if (A[i] <= points[j] && points[j] <= B[i]) {
        new_ways[j][1] += pref[j];
      }
      for (int k = 0; k < N; k++) {
        norm(new_ways[j][k] += ways[j][k]);
        if (A[i] <= points[j] && points[j] <= B[i]) {
          norm(new_ways[j][k + 1] += ways[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 * new_ways[j][k] * choose_weight[j][k]) % MOD;
      }
    }
    ways = new_ways;
  }
  cout << pref[M] << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42