제출 #197928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197928		quocnguyen1012	Boat (APIO16_boat)	C++14	100 / 100	873 ms	2608 KiB

boat

#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][1005];
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];
}

컴파일 시 표준 에러 (stderr) 메시지

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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42