oj.uz

답안 #245322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245322 2020-07-06T04:00:42 Z neihcr7j Boat (APIO16_boat) C++14
9 / 100
 626 ms 5112 KB 
#include<bits/stdc++.h>

#define M 1000000007
#define maxn 502

using namespace std;
typedef long long ll;

inline ll norm(ll a) {
  return (a < 0 ? a + M : (a >= M ? a - M : a));
}

inline ll mul(ll a, ll b) {
  return a * b % M;
}

ll power(ll a, ll b) {
  if (b == 0) return 1;
  if (b&1) return mul(power(a, b - 1), a);
  ll t = power(a, b / 2);
  return mul(t, t);
}

ll gt[maxn * 2], igt[maxn * 2];

void precalc(){
  int n = 1000;

  gt[0] = 1;
  for (int i = 1; i <= n; ++i)
    gt[i] = mul(gt[i - 1], i);

  igt[n] = power(gt[n], M - 2);

  for (int i = n - 1; i >= 0; --i)
    igt[i] = mul(igt[i + 1], i + 1);
}

ll C(int n, int k) {
  return mul(mul(gt[n], igt[k]), igt[n - k]);
}


int n;

int l[maxn], r[maxn];
vector < pair < int, int > > seg;
vector < vector < int > > a;
vector < int > leng;

ll dp[maxn * 4][maxn];

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  precalc();

  cin >> n;

  vector < int > ret;

  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];

    ret.push_back(l[i]);
    ret.push_back(r[i]);
  }

  sort(ret.begin(), ret.end());

  seg.push_back({ret[0], ret[0]});

  for (int i = 1; i < ret.size(); ++i)
    if (ret[i] != ret[i - 1]) {
      if (i == ret.size() || ret[i] != ret[i + 1]) {
        seg.push_back({ret[i - 1] + 1, ret[i]});
        continue;
      }

      if (ret[i - 1] + 1 != ret[i])
        seg.push_back({ret[i - 1] + 1, ret[i] - 1});
      seg.push_back({ret[i], ret[i]});
    }

  a = vector < vector < int > >(seg.size(), vector < int >(0, 0));
  leng = vector < int > (seg.size(), 0);

  for (int i = 0; i < seg.size(); ++i) {
    for (int j = 1; j <= n; ++j)
      if (l[j] <= seg[i].first && seg[i].second <= r[j])
        a[i].push_back(j);
    leng[i] = seg[i].second - seg[i].first + 1;
  }

  ll ans = 0;

  for (int i = 0; i < seg.size(); ++i) {
    ll l = leng[i];

    vector < ll > c(a[i].size() + 1, 0), val(a[i].size() + 1, 0);

    c[0] = 1;

    for (int k = 1; k <= a[i].size(); ++k) {
      if (k <= l)
        c[k] = mul(mul(c[k - 1], l - k + 1), power(k, M - 2));

      for (int x = k; x > 0; --x)
        if (x <= l)
          val[k] = norm(val[k] + mul(c[x], C(k - 1, x - 1)));
    }

     int index = 0;

    for (int k = 0; k <= n; ++k) {
      ll res = (k == 0 ? 1 : 0);

      for (int j = 0; j < i; ++j)
        res = norm(res + dp[j][k]);

      while (index < a[i].size() && a[i][index] <= k)
        index++;

      for (int j = index; j < a[i].size(); ++j)
        dp[i][a[i][j]] = norm(dp[i][a[i][j]] + mul(res, val[j - index + 1]));

      ans = norm(ans + dp[i][k]);
    }
  }

  cout << ans;

  return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < ret.size(); ++i)
                   ~~^~~~~~~~~~~~
boat.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (i == ret.size() || ret[i] != ret[i + 1]) {
           ~~^~~~~~~~~~~~~
boat.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:99:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 1; k <= a[i].size(); ++k) {
                     ~~^~~~~~~~~~~~~~
boat.cpp:123:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (index < a[i].size() && a[i][index] <= k)
              ~~~~~~^~~~~~~~~~~~~
boat.cpp:126:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = index; j < a[i].size(); ++j)
                           ~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 2552 KB Output is correct
2 Correct 436 ms 2424 KB Output is correct
3 Correct 428 ms 2424 KB Output is correct
4 Correct 437 ms 2424 KB Output is correct
5 Correct 429 ms 2424 KB Output is correct
6 Correct 430 ms 2424 KB Output is correct
7 Correct 428 ms 2424 KB Output is correct
8 Correct 431 ms 2424 KB Output is correct
9 Correct 433 ms 2680 KB Output is correct
10 Correct 437 ms 2480 KB Output is correct
11 Correct 431 ms 2424 KB Output is correct
12 Correct 432 ms 2424 KB Output is correct
13 Correct 432 ms 2424 KB Output is correct
14 Correct 434 ms 2424 KB Output is correct
15 Correct 443 ms 2488 KB Output is correct
16 Correct 19 ms 896 KB Output is correct
17 Correct 21 ms 896 KB Output is correct
18 Correct 20 ms 896 KB Output is correct
19 Correct 22 ms 1024 KB Output is correct
20 Correct 20 ms 896 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 2552 KB Output is correct
2 Correct 436 ms 2424 KB Output is correct
3 Correct 428 ms 2424 KB Output is correct
4 Correct 437 ms 2424 KB Output is correct
5 Correct 429 ms 2424 KB Output is correct
6 Correct 430 ms 2424 KB Output is correct
7 Correct 428 ms 2424 KB Output is correct
8 Correct 431 ms 2424 KB Output is correct
9 Correct 433 ms 2680 KB Output is correct
10 Correct 437 ms 2480 KB Output is correct
11 Correct 431 ms 2424 KB Output is correct
12 Correct 432 ms 2424 KB Output is correct
13 Correct 432 ms 2424 KB Output is correct
14 Correct 434 ms 2424 KB Output is correct
15 Correct 443 ms 2488 KB Output is correct
16 Correct 19 ms 896 KB Output is correct
17 Correct 21 ms 896 KB Output is correct
18 Correct 20 ms 896 KB Output is correct
19 Correct 22 ms 1024 KB Output is correct
20 Correct 20 ms 896 KB Output is correct
21 Incorrect 626 ms 5112 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 1280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 2552 KB Output is correct
2 Correct 436 ms 2424 KB Output is correct
3 Correct 428 ms 2424 KB Output is correct
4 Correct 437 ms 2424 KB Output is correct
5 Correct 429 ms 2424 KB Output is correct
6 Correct 430 ms 2424 KB Output is correct
7 Correct 428 ms 2424 KB Output is correct
8 Correct 431 ms 2424 KB Output is correct
9 Correct 433 ms 2680 KB Output is correct
10 Correct 437 ms 2480 KB Output is correct
11 Correct 431 ms 2424 KB Output is correct
12 Correct 432 ms 2424 KB Output is correct
13 Correct 432 ms 2424 KB Output is correct
14 Correct 434 ms 2424 KB Output is correct
15 Correct 443 ms 2488 KB Output is correct
16 Correct 19 ms 896 KB Output is correct
17 Correct 21 ms 896 KB Output is correct
18 Correct 20 ms 896 KB Output is correct
19 Correct 22 ms 1024 KB Output is correct
20 Correct 20 ms 896 KB Output is correct
21 Incorrect 626 ms 5112 KB Output isn't correct
22 Halted 0 ms 0 KB -