oj.uz

Submission #197925

# Submission time Handle Problem Language Result Execution time Memory
197925 2020-01-24T09:33:10 Z quocnguyen1012 Boat (APIO16_boat) C++14
0 / 100
 10 ms 1272 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;

void add(int & a, int b)
{
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

int mul(int a, int b)
{
  return 1ll * a * b % mod;
}

int power(int a, int b)
{
  if (b == 0) return 1;
  int res = power(a, b / 2);
  if (b & 1) return 1ll * res * res % mod * a % mod;
  return 1ll * res * res % mod;
}

int f[505][505];
int N, a[505], b[505], inv[505], fac[505];

int C(int k, int n)
{
  if (k > n) return 0;
  return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  fac[0] = 1;
  for (int i = 1; i < 505; ++i){
    inv[i] = power(i, mod - 2);
    fac[i] = mul(fac[i - 1], i);
  }
  vector<int> seg;
  for (int i = 1; i <= N; ++i){
    cin >> a[i] >> b[i];
    seg.pb(a[i] - 1); seg.pb(b[i]);
  }
  sort(seg.begin(), seg.end()); seg.erase(unique(seg.begin(), seg.end()), seg.end());
  for (int i = 0; i < (int) seg.size(); ++i){
    f[0][i] = 1;
  }
  for (int i = 1; i <= N; ++i){
    a[i] = lower_bound(seg.begin(), seg.end(), a[i]) - seg.begin();
    b[i] = lower_bound(seg.begin(), seg.end(), b[i]) - seg.begin();
  }
  for (int i = 1; i <= N; ++i){
    f[i][0] = 1;
    for (int val = a[i]; val <= b[i]; ++val){
      int can = seg[val] - seg[val - 1];
      f[i][val] = mul(f[i - 1][val - 1], can);
      int cnt = 1;
      for (int k = i - 1; k >= 1; --k){
        if (a[k] <= val && val <= b[k]){
          ++cnt;
          add(f[i][val], mul(f[k - 1][val - 1], C(cnt, can)));
        }
      }
    }
    for (int j = 1; j < (int)seg.size(); ++j){
      add(f[i][j], f[i][j - 1]);
      add(f[i][j], f[i - 1][j]);
      add(f[i][j], -f[i - 1][j - 1]);
    }
  }
  add(f[N][int(seg.size()) - 1], -1);
  cout << f[N][int(seg.size()) - 1];
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
boat.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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