Submission #810835

#	Time	Username	Problem	Language	Result	Execution time	Memory
810835		abczz	Boat (APIO16_boat)	C++14	100 / 100	477 ms	460 KiB

boat

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

const ll M = 1e9 + 7;
vector<array<ll, 3> > V;
vector <array<ll, 2> > U;
bool B[500];
ll dp[500], C[501];
ll n, a, b, s, z, p, f, cnt, tmp, cur, fact[501], inv[501];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  fact[0] = fact[1] = inv[0] = inv[1] = 1;
  for (ll i=2; i<=n; ++i) {
    fact[i] = fact[i-1] * i;
    fact[i] %= M;
    inv[i] = (M-(((M/i) * inv[M%i])%M))%M;
  }
  for (int i=2; i<=n; ++i) {
    inv[i] *= inv[i-1];
    inv[i] %= M;
  }
  for (int i=0; i<n; ++i) {
    cin >> a >> b;
    V.push_back({a, i, 0});
    V.push_back({b+1, i, 1});
  }
  sort(V.begin(), V.end());
  for (int i=0; i+1<V.size(); ++i) {
    if (!V[i][2]) {
      B[V[i][1]] = 1;
    }
    else {
      B[V[i][1]] = 0;
    }
    z = V[i+1][0]-V[i][0];
    if (!z) continue;
    U.clear();
    s = 1;
    for (int j=0; j<n; ++j) {
      if (B[j]) U.push_back({j, s});
      s += dp[j];
      s %= M;
    }
    for (ll j=1; j<=U.size(); ++j) {
      if (j > 1 && z < 2) {
        C[j] = 0;
        continue;
      }
      if (j == 1) {
        C[j] = z;
        continue;
      }
      else if (j == 2) {
        C[j] = ((z * (z-1))/2) % M;
        continue;
      }
      C[j] = 0;
      p = (z * (z-1))%M;
      for (ll k=2; k<=min(j, z); ++k) {
        cur = 1;
        cur *= (((fact[j-2] * inv[j-k])%M) * inv[k-2])%M;
        cur *= (p * inv[k]) % M;
        cur %= M;
        C[j] += cur;
        C[j] %= M;
        p *= (z-k);
        p %= M;
      }
    }
    for (int j=0; j<U.size(); ++j) {
      for (int k=j; k<U.size(); ++k) {
        //cout << U[j][0] << " " << U[k][0] << ":" << U[j][1] << "*" << C[k-j+1] << endl;
        dp[U[k][0]] += ((U[j][1] * C[k-j+1]) % M);
        dp[U[k][0]] %= M;
      }
    }
    /*for (int j=0; j<n; ++j) {
      cout << dp[j] << " ";
    }
    cout << endl;*/
  }
  for (int i=0; i<n; ++i) {
    f += dp[i];
    f %= M;
  }
  cout << f << '\n';
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0; i+1<V.size(); ++i) {
      |                 ~~~^~~~~~~~~
boat.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (ll j=1; j<=U.size(); ++j) {
      |                  ~^~~~~~~~~~
boat.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int j=0; j<U.size(); ++j) {
      |                   ~^~~~~~~~~
boat.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |       for (int k=j; k<U.size(); ++k) {
      |                     ~^~~~~~~~~

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