Submission #48487

#	Time	Username	Problem	Language	Result	Execution time	Memory
48487		octopuses	Boat (APIO16_boat)	C++17	100 / 100	1517 ms	17512 KiB

boat

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define M (ll)(1e9 + 7)

using namespace std;
const int N = 1020;

ll pw(ll x, ll y)
{
  if(y == 0)
    return 1ll;
  ll ans = pw(x, y / 2);
  ans = (ans * ans) % M;
  if(y % 2 == 1)
    ans = (x * ans) % M;
  return ans;
}

ll F[N];

inline ll cnt(ll n, ll k)
{
  if(n - k < k)
    k = n - k;
  ll s = 1ll;
  for(int i = n; i > n - k; -- i)
    s = (s * i) % M;
  s = (s * F[k]) % M;
  return s;
}

int n, tot;
int x[N], y[N], a[N];
ll C[N][N], A[N][N], S[N];
map < int, int > mp;
vector < int > ar;


int main()
{
  F[0] = 1;
  for(int i = 1; i < N; ++ i)
    F[i] = (F[i - 1] * i) % M;
  for(int i = 0; i < N; ++ i)
    F[i] = pw(F[i], M - 2);
  scanf("%d", &n);
  for(int i = 0; i < n; ++ i)
  {
    scanf("%d %d", &x[i], &y[i]);
    mp[x[i]] = 1;
    mp[y[i] + 1] = 1;
  }
  tot = 0;
  for(map < int, int >::iterator it = mp.begin(); it != mp.end(); ++ it)
  {
    ar.push_back(it -> fr);
    it -> sc = tot ++;
  }
  for(int i = 1; i < tot; ++ i)
    a[i] = ar[i] - ar[i - 1];
  for(int i = 0; i < n; ++ i)
  {
    y[i] = mp[y[i] + 1] + 1;
    x[i] = mp[x[i]] + 1;
  }
  for(int i = 1; i < tot; ++ i)
    for(int j = 1; j <= n; ++ j)
      C[i][j] = cnt(a[i] + j - 1, j);
  S[0] = 1; ll s;
  for(int k = 0; k < n; ++ k)
  {
    s = 0;
    for(int i = 0; i < x[k]; ++ i)
      s = (s + S[i]) % M;
    for(int i = x[k]; i < y[k]; ++ i)
    {
      A[i][0] = s;
      s = (s + S[i]) % M;
      S[i] = 0;
      for(int j = n; j > 0; -- j)
      {
        A[i][j] = A[i][j - 1];
        S[i] = ((A[i][j] * C[i][j]) % M + S[i]) % M;
      }
    }
  }
  s = 0;
  for(int i = 1; i < tot; ++ i)
    s = (s + S[i]) % M;
  cout << s << endl;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
boat.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x[i], &y[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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