oj.uz

Submission #46418

# Submission time Handle Problem Language Result Execution time Memory
46418 2018-04-20T09:00:42 Z Trans Boat (APIO16_boat) C++14
0 / 100
 7 ms 3832 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repd(i, a, b) for (int i = (a) - 1; i >= b; i--)
#define pb push_back
#define fi first
#define se second

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 505;

int n, a[maxn], b[maxn];
map<int, int> mm;
ll dp[maxn][maxn * 2];
vector<ll> vi;

ll power_mod(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b % 2) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

int main() {
  cin >> n;

  mm[0];
  rep(i, 0, n) {
    cin >> a[i] >> b[i];
    mm[a[i] - 1]++;
    mm[b[i]]++;
  }

  int cnt = 0;
  for (auto it = mm.begin(); it != mm.end(); it++) {
    it->se = cnt++;
    vi.pb(it->fi);
  }

  ll ans = 0;
  rep(i, 0, n) {
    int hi = mm[b[i]] + 1;
    int lo = mm[a[i] - 1] + 1;
    dp[i][0] = 1;
    repd(k, hi, lo) {
      ll ways = (vi[k] - vi[k - 1]) * (i ? dp[i - 1][k - 1] : 1);
      ll range = vi[k] - vi[k - 1];
      ll now = range;
      repd(j, i, 0) {
        if (b[j] < vi[k - 1] + 1 || a[j] > vi[k]) break;
        now = now * power_mod(i - j + 1, mod - 2) % mod;
        now = now * (range + i - j) % mod;
        ways += now * (j ? dp[j - 1][k - 1] : 1) % mod;
        ways %= mod;
      }
      // if (i == 1) cout << ways << endl;
      dp[i][k] = ways;
    }
    rep(k, 1, hi) {
      dp[i][k] = (dp[i][k] + dp[i][k - 1]) % mod;
      ans = dp[i][k];
    }
  }
  // cout << dp[1][2] << endl;
  cout << ans;
  return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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