oj.uz

답안 #231292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231292 2020-05-13T10:15:36 Z AlexLuchianov Boat (APIO16_boat) C++14
0 / 100
 2000 ms 4352 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <map>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500;
int const modulo = 1000000007;

class ModuloRing{
private:
  void gcd(int a, int b, int &x, int &y){
    if(b == 0){
      x = 1;
      y = 0;
    } else {
      gcd(b, a % b, x, y);
      int aux = x;
      x = y;
      y = aux - a / b * y;
    }
  }
public:
  int number;
  ModuloRing(ll number_ = 0){
    number = number_ % modulo;
  }
  ModuloRing operator + (ModuloRing a) {
    return {number + a.number};
  }
  ModuloRing operator - (ModuloRing a) {
    return {modulo + number - a.number};
  }
  ModuloRing operator * (ModuloRing a) {
    return {1LL * number * a.number};
  }
  ModuloRing operator / (ModuloRing a) {
    int x, y;
    gcd(a.number, modulo, x, y);
    x %= modulo;
    if(x < 0)
      x += modulo;
    return 1LL * number * x;
  }
};

map<int,int> code;
vector<int> dist;

int a[1 + nmax], b[1 + nmax];

void normalize(int n){
  vector<int> temp;
  temp.push_back(0);
  for(int i = 1; i <= n; i++){
    temp.push_back(a[i]);
    temp.push_back(b[i]);
  }
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  dist = temp;
  for(int i = 0; i < temp.size(); i++)
    code[temp[i]] = i;
  for(int i = 1;i <= n; i++){
    a[i] = code[a[i]];
    b[i] = code[b[i]];
  }

}

ModuloRing choose[5 + 2 * nmax][1 + nmax];
ModuloRing dp[5 + nmax][5 + 2 * nmax];
ModuloRing fact[5 + nmax];

void computefact(){
  fact[0] = 1;
  for(int i = 1;i <= nmax; i++)
    fact[i] = fact[i - 1] * i;
}

ModuloRing comb(int n, int k){
  if(n < k)
    return 0;
  if(n <= nmax)
    return fact[n] / fact[k] / fact[n - k];

  ModuloRing result(1);
  for(int i = n - k + 1; i <= n; i++)
    result = result * i;
  for(int i = 1; i <= k; i++)
    result = result / i;
  return result;
}

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++) {
    cin >> a[i] >> b[i];
    b[i]++;
  }
  normalize(n);
  computefact();

  for(int i = 1; i < dist.size() - 1; i++) {
    int d = dist[i + 1] - dist[i];
    for(int h = 1;h <= n; h++) {
      ModuloRing snap = comb(d, h);
      for(int j = h; j <= n; j++)
        choose[i][j] = choose[i][j] + comb(j - 1, h - 1) * snap;
    }
  }

  return 0;

  for(int i = 0; i < dist.size() - 1; i++)
    dp[0][i] = 1;

  for(int i = 1;i <= n; i++){
    for(int j = a[i]; j < b[i]; j++){
      int _count = 1;
      for(int i2 = i - 1; 0 <= i2; i2--){
        dp[i][j] = dp[i][j] + dp[i2][j - 1] * choose[j][_count];
        if(a[i2] <= j && j < b[i2])
          _count++;
      }
    }
    for(int j = 1; j < dist.size() - 1; j++) {
      dp[i][j] = dp[i][j] + dp[i][j - 1];
    }
  }

  ModuloRing result(0);
  for(int i = 1;i <= n; i++)
    result = result + dp[i][dist.size() - 2];
  cout << result.number;
  return 0;
}

/*
2
1 10
5 20
*/

Compilation message

boat.cpp: In function 'void normalize(int)':
boat.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < dist.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~~~
boat.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dist.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~~~
boat.cpp:136:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 1; j < dist.size() - 1; j++) {
                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 349 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -