Submission #970330

#	Time	Username	Problem	Language	Result	Execution time	Memory
970330		duckindog	Boat (APIO16_boat)	C++17	100 / 100	486 ms	2648 KiB

boat

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 500 + 10,
          M = 1'000'000'007;
int n;
int a[N], b[N];

int f[1'010][N];
void add(auto& x, const auto& y) { 
  x += y;
  if (x >= M) x -= M;
}

int powder(int a, int b) { 
  int ret = 1;
  while (b) { 
    if (b & 1) ret = 1ll * ret * a % M;
    a = 1ll * a * a % M;
    b >>= 1;
  }
  return ret;
}

int inv[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];

  for (int i = 2; i <= n + 1; ++i) inv[i] = powder(i, M - 2);

  vector<int> rrh(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) rrh.push_back(b[i] + 1);
  sort(rrh.begin(), rrh.end());
  rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
  
  for (int i = 0; i < rrh.size(); ++i) f[i][0] = 1;
  for (int i = 1; i < rrh.size(); ++i) { 
    for (int j = 1; j <= n; ++j) { 
      auto& ret = f[i][j];
      ret = f[i - 1][j];
      if (a[j] > rrh[i - 1] || rrh[i - 1] > b[j]) continue;
      
      int len = rrh[i] - rrh[i - 1];
      int mul = len, cnt = 1;

      for (int t = j - 1; t >= 0; --t) {
        add(ret, 1ll * f[i - 1][t] * mul % M);
        if (a[t] <= rrh[i - 1] && rrh[i - 1] <= b[t]) { 
          mul = 1ll * mul * (len + cnt) % M * inv[cnt + 1] % M;
          cnt += 1;
        }
      }
    }
  }
  
  int answer = 0;
  for (int i = 1; i <= n; ++i) add(answer, f[rrh.size() - 1][i]);

  cout << answer << "\n";
}

Compilation message (stderr)

boat.cpp:11:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   11 | void add(auto& x, const auto& y) {
      |          ^~~~
boat.cpp:11:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   11 | void add(auto& x, const auto& y) {
      |                         ^~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 0; i < rrh.size(); ++i) f[i][0] = 1;
      |                   ~~^~~~~~~~~~~~
boat.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 1; i < rrh.size(); ++i) {
      |                   ~~^~~~~~~~~~~~

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