oj.uz

Submission #499666

# Submission time Handle Problem Language Result Execution time Memory
499666 2021-12-29T08:05:48 Z keta_tsimakuridze Boat (APIO16_boat) C++14
27 / 100
 1248 ms 4400 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],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 - 1, x - 1) % mod + c[len][x - 1]) % mod;
       }
       for(int j = 1; 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());
            int y =  100000;

            dp[0][0] = 1;

            int cur = 0;
            for(int i = 1; i < x.size(); i++) {
                   if(x[i] != x[i - 1]) go(++cur, x[i], x[i]);
                   if(i + 1 < x.size() && 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:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:68: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]
   68 |             for(int i = 1; i < x.size(); i++) {
      |                            ~~^~~~~~~~~~
boat.cpp:70:29: 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]
   70 |                    if(i + 1 < x.size() && x[i] + 1 < x[i + 1]) go(++cur, x[i] + 1, x[i + 1] - 1);
      |                       ~~~~~~^~~~~~~~~~
boat.cpp:63:17: warning: unused variable 'y' [-Wunused-variable]
   63 |             int y =  100000;
      |                 ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1104 KB Output is correct
2 Correct 27 ms 1188 KB Output is correct
3 Correct 24 ms 1068 KB Output is correct
4 Correct 23 ms 1120 KB Output is correct
5 Correct 24 ms 1100 KB Output is correct
6 Correct 32 ms 1100 KB Output is correct
7 Correct 26 ms 1124 KB Output is correct
8 Correct 25 ms 1100 KB Output is correct
9 Correct 25 ms 1100 KB Output is correct
10 Correct 26 ms 1100 KB Output is correct
11 Correct 24 ms 1100 KB Output is correct
12 Correct 24 ms 1068 KB Output is correct
13 Correct 24 ms 1100 KB Output is correct
14 Correct 27 ms 1100 KB Output is correct
15 Correct 24 ms 1100 KB Output is correct
16 Correct 11 ms 1124 KB Output is correct
17 Correct 11 ms 1120 KB Output is correct
18 Correct 11 ms 1124 KB Output is correct
19 Correct 12 ms 1124 KB Output is correct
20 Correct 12 ms 1132 KB Output is correct

Subtask #4
0 / 42.0

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