oj.uz

Submission #41678

# Submission time Handle Problem Language Result Execution time Memory
41678 2018-02-20T12:14:38 Z gabrielsimoes Boat (APIO16_boat) C++14
9 / 100
 67 ms 1076 KB 
#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(inv[MOD % i] - 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 = 0;
      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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 7 ms 624 KB Output is correct
4 Correct 7 ms 628 KB Output is correct
5 Correct 7 ms 656 KB Output is correct
6 Correct 6 ms 668 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 6 ms 900 KB Output is correct
12 Correct 8 ms 912 KB Output is correct
13 Correct 6 ms 924 KB Output is correct
14 Correct 6 ms 936 KB Output is correct
15 Correct 6 ms 1076 KB Output is correct
16 Correct 3 ms 1076 KB Output is correct
17 Correct 3 ms 1076 KB Output is correct
18 Correct 3 ms 1076 KB Output is correct
19 Correct 3 ms 1076 KB Output is correct
20 Correct 3 ms 1076 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 7 ms 624 KB Output is correct
4 Correct 7 ms 628 KB Output is correct
5 Correct 7 ms 656 KB Output is correct
6 Correct 6 ms 668 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 6 ms 900 KB Output is correct
12 Correct 8 ms 912 KB Output is correct
13 Correct 6 ms 924 KB Output is correct
14 Correct 6 ms 936 KB Output is correct
15 Correct 6 ms 1076 KB Output is correct
16 Correct 3 ms 1076 KB Output is correct
17 Correct 3 ms 1076 KB Output is correct
18 Correct 3 ms 1076 KB Output is correct
19 Correct 3 ms 1076 KB Output is correct
20 Correct 3 ms 1076 KB Output is correct
21 Incorrect 67 ms 1076 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 7 ms 624 KB Output is correct
4 Correct 7 ms 628 KB Output is correct
5 Correct 7 ms 656 KB Output is correct
6 Correct 6 ms 668 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 6 ms 900 KB Output is correct
12 Correct 8 ms 912 KB Output is correct
13 Correct 6 ms 924 KB Output is correct
14 Correct 6 ms 936 KB Output is correct
15 Correct 6 ms 1076 KB Output is correct
16 Correct 3 ms 1076 KB Output is correct
17 Correct 3 ms 1076 KB Output is correct
18 Correct 3 ms 1076 KB Output is correct
19 Correct 3 ms 1076 KB Output is correct
20 Correct 3 ms 1076 KB Output is correct
21 Incorrect 67 ms 1076 KB Output isn't correct
22 Halted 0 ms 0 KB -