Submission #41680

#	Time	Username	Problem	Language	Result	Execution time	Memory
41680		gabrielsimoes	Boat (APIO16_boat)	C++14	100 / 100	708 ms	1364 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1'000'000'007;

inline ll mod(ll a) { return a %= MOD, a < 0 ? a + MOD : a; }

int main() {
  int n;
  scanf("%d", &n);

  vector<int> limits;
  int va[n + 1], vb[n + 1];
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &va[i], &vb[i]);
    vb[i]++;
    limits.push_back(va[i]);
    limits.push_back(vb[i]);
  }

  sort(limits.begin(), limits.end());
  limits.resize(unique(limits.begin(), limits.end()) - limits.begin());

  ll dp[n + 1], sum[n + 1], inv[n + 1];

  memset(dp, 0, sizeof(dp));
  memset(sum, 0, sizeof(sum));

  sum[0] = 1;

  inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = mod(-(MOD / i) * inv[MOD % i]);

  for (int region = 1; region < limits.size(); region++) {
    ll len = limits[region] - limits[region - 1];

    for (int i = 1; i <= n; i++) {
      sum[i] = mod(sum[i - 1] + dp[i]);

      if (va[i] >= limits[region] || vb[i] <= limits[region - 1]) continue;

      ll bin = 1;
      for (int k = i, cnt = 0; k >= 1; k--) {
        if (va[k] >= limits[region] || vb[k] <= limits[region - 1]) continue;

        cnt++;
        bin = mod(mod(bin * (len + cnt - 2)) * inv[cnt]);

        if (cnt == 1) {
          dp[i] += mod(sum[k - 1] * len);
        } else {
          dp[i] += mod(sum[k - 1] * bin);
        }
      }

      dp[i] %= MOD;
    }
  }

  ll ans = 0;
  for (int i = 1; i <= n; i++) ans += dp[i];
  printf("%lld\n", ans % MOD);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int region = 1; region < limits.size(); region++) {
                               ^
boat.cpp:11:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
boat.cpp:16:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &va[i], &vb[i]);
                                   ^

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