oj.uz

Submission #197921

# Submission time Handle Problem Language Result Execution time Memory
197921 2020-01-24T09:19:33 Z quocnguyen1012 Boat (APIO16_boat) C++14
27 / 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];

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;
  for (int i = 1; i < 505; ++i){
    inv[i] = power(i, mod - 2);
  }
  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, way = can - 1;
      for (int k = i - 1; k >= 1; --k){
        if (a[k] <= val && val <= b[k]){
          way = mul(way, can++);
          way = mul(way, inv[++cnt]);
          add(f[i][val], mul(f[k - 1][val - 1], way));
        }
      }
    }
    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:40: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:41: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
27.0 / 27.0

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

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 -