oj.uz

답안 #499653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499653 2021-12-29T07:03:13 Z keta_tsimakuridze Boat (APIO16_boat) C++14
0 / 100
 1343 ms 6388 KB 
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 505, mod = 1e9 + 7; // !
int t, L[N], R[N], n, dp[N][N], pref[N][N], fact[N], invfact[N], c[N][N], cc[N], p[N];
vector<int> x;
int pwr(int u,int v) {
            int ans = 1;
            while(v) {
                        if(v % 2) ans = u * ans % mod;
                        v /= 2; u = u * u % mod;
            }
            return ans;
}
int C(int a,int b) {
            if(a < b) return 0;
            int x = 1;
            for(int j = a - b + 1; j <= a; j++) x = x * j % mod;
            return x * invfact[b] % mod;
}
int C2(int a,int b) {
            if(a < b) return 0;
            return fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}


void go(int i,int l, int r) {
       
       for(int j = 0; j <= n; j++) cc[j] = C(r - l + 1, j);
       for(int len = 1; len <= n; len++) {
            for(int x = 1; x <= len; x++) c[len][x] = (cc[x] * C2(len, x - 1) % mod + c[len][x - 1]) % mod;
       }
       for(int j = 0; j <= n; j++) {
            p[j] = p[j - 1];
            if(L[j] <= l && r <= R[j]) p[j]++;
            if(!(p[j] - p[j - 1])) continue; 
            for(int k = 0; k <= j; k++) {
                        dp[j][i] += dp[k][i - 1] * c[p[j] - p[k]][p[j] - p[k]] % mod;
                        dp[j][i] %= mod;
            }
       }
       for(int j = 0; j <= n; j++) {
            dp[j][i] = (dp[j][i - 1] + dp[j][i]) % mod;
       }
}
main(){
            cin >> n;
            fact[0] = invfact[0] = 1;
            for(int i = 1; i <= n; i++) {
                        cin >> L[i] >> R[i];
                        x.push_back(L[i]);
                        x.push_back(R[i]);
                        fact[i] = fact[i - 1] * i % mod;
                        invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
            }
            x.push_back(-1);
            sort(x.begin(), x.end());

            dp[0][0] = 1;
            for(int i = 0; i <= n; i++) pref[i][0] = 1;
            int cur = 0;
            for(int i = 1; i < x.size(); i++) {
                   //     (x[i] + 1 ... x[i + 1] )
                   if(x[i] != x[i - 1]) go(++cur, x[i], x[i]);
                   if(x[i] + 1 < x[i + 1]) go(++cur, x[i] + 1, x[i + 1] - 1);
            }
            int ans = 0;
            for(int i = 1; i <= n; i++) {
                        ans = (ans + dp[i][cur]) % mod;
            }
            cout << ans;
}

Compilation message

boat.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:65:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int i = 1; i < x.size(); i++) {
      |                            ~~^~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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