Submission #231294

#	Time	Username	Problem	Language	Result	Execution time	Memory
231294		AlexLuchianov	Boat (APIO16_boat)	C++14	100 / 100	1860 ms	5496 KiB

boat

#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 combfast[1 + nmax][1 + nmax];

void precompute(){
  combfast[0][0] = 1;
  for(int i = 1;i <= nmax; i++) {
    combfast[i][0] = 1;
    for(int j = 1; j <= i; j++)
      combfast[i][j] = combfast[i - 1][j - 1] + combfast[i - 1][j];
  }
}

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

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

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

  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;
    }
  }


  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 (stderr)

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:123:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < dist.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~~~
boat.cpp:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dist.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~~~
boat.cpp:145:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 1; j < dist.size() - 1; j++) {
                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42