oj.uz

Submission #197927

# Submission time Handle Problem Language Result Execution time Memory
197927 2020-01-24T09:37:17 Z quocnguyen1012 Boat (APIO16_boat) C++14
27 / 100
 13 ms 1400 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> comp;
  for (int i = 1; i <= N; ++i){
    cin >> a[i] >> b[i];
    comp.pb(a[i] - 1); comp.pb(b[i]);
  }
  sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end());
  for (int i = 0; i < (int) comp.size(); ++i){
    f[0][i] = 1;
  }
  for (int i = 1; i <= N; ++i){
    a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
    b[i] = lower_bound(comp.begin(), comp.end(), b[i]) - comp.begin();
  }
  for(int i = 1 ; i <= N ; ++i){
    assert(a[i]);
    f[i][0] = 1;
    for(int j = a[i] ; j <= b[i] ; ++j) {
      f[i][j] = mul(f[i - 1][j - 1],comp[j] - comp[j - 1]);
      int cnt = 1;
      int Max = comp[j] - comp[j - 1];
      int way = Max - 1;
      for(int k = i - 1 ; k ; --k){
        if (a[k] <= j && j <= b[k]) {
          way = mul(way,Max++);
          way = mul(way,inv[++cnt]);
          add(f[i][j],mul(f[k - 1][j - 1],way));
        }
      }
    }
    for(int j = 1 ; j < comp.size() ; ++j){
      add(f[i][j],f[i - 1][j]),
      add(f[i][j],f[i][j - 1]),
      add(f[i][j],-f[i - 1][j - 1]);
    }
  }
  add(f[N][int(comp.size()) - 1], -1);
  cout << f[N][int(comp.size()) - 1];
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 1 ; j < comp.size() ; ++j){
                     ~~^~~~~~~~~~~~~
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 1400 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 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 508 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 10 ms 504 KB Output is correct
7 Correct 9 ms 504 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 10 ms 508 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 636 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 4 ms 504 KB Output is correct
20 Correct 5 ms 632 KB Output is correct

Subtask #4
0 / 42.0

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