oj.uz

Submission #48485

# Submission time Handle Problem Language Result Execution time Memory
48485 2018-05-14T12:20:28 Z octopuses Boat (APIO16_boat) C++17
0 / 100
 415 ms 12400 KB 
#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 = 1;
  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]);
  cout << s;
}

Compilation message

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 12400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 12400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 12400 KB Output isn't correct
2 Halted 0 ms 0 KB -