oj.uz

Submission #499672

# Submission time Handle Problem Language Result Execution time Memory
499672 2021-12-29T08:15:16 Z keta_tsimakuridze Boat (APIO16_boat) C++14
36 / 100
 2000 ms 5624 KB 
#include<bits/stdc++.h>
#define ll 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][4 *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 = (ll)u * ans % mod;
                        v /= 2; u = (ll)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 = (ll)x * j % mod;
            return (ll)x * invfact[b] % mod;
}
int C2(int a,int b) {
            if(a < b) return 0;
            return (ll)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] = ((ll)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] += (ll)dp[k][i - 1] * c[p[j] - p[k]][p[j] - p[k]] % mod;
                        if(dp[j][i] >= mod) dp[j][i] -= mod;
            }
       }
       for(int j = 0; j <= n; j++) {
            dp[j][i] += dp[j][i - 1];
            if(dp[j][i] >= mod) dp[j][i] -= mod;
       }
}
main(){
			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
            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] = (ll)fact[i - 1] * i % mod;
                        invfact[i] = (ll)invfact[i - 1] * pwr(i, mod - 2) % mod;
            }
            x.push_back(-1);
            sort(x.begin(), x.end());
            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:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i = 1; i < x.size(); i++) {
      |                            ~~^~~~~~~~~~
boat.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                    if(i + 1 < x.size() && x[i] + 1 < x[i + 1]) go(++cur, x[i] + 1, x[i + 1] - 1);
      |                       ~~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1377 ms 5328 KB Output is correct
2 Correct 1400 ms 5456 KB Output is correct
3 Correct 1386 ms 5212 KB Output is correct
4 Correct 1353 ms 5180 KB Output is correct
5 Correct 1365 ms 5336 KB Output is correct
6 Correct 1344 ms 5280 KB Output is correct
7 Correct 1326 ms 5412 KB Output is correct
8 Correct 1320 ms 5404 KB Output is correct
9 Correct 1331 ms 5232 KB Output is correct
10 Correct 1329 ms 5360 KB Output is correct
11 Correct 1324 ms 5392 KB Output is correct
12 Correct 1354 ms 5328 KB Output is correct
13 Correct 1326 ms 5248 KB Output is correct
14 Correct 1336 ms 5256 KB Output is correct
15 Correct 1329 ms 5152 KB Output is correct
16 Correct 237 ms 3828 KB Output is correct
17 Correct 254 ms 3604 KB Output is correct
18 Correct 248 ms 3728 KB Output is correct
19 Correct 263 ms 3672 KB Output is correct
20 Correct 248 ms 3660 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1377 ms 5328 KB Output is correct
2 Correct 1400 ms 5456 KB Output is correct
3 Correct 1386 ms 5212 KB Output is correct
4 Correct 1353 ms 5180 KB Output is correct
5 Correct 1365 ms 5336 KB Output is correct
6 Correct 1344 ms 5280 KB Output is correct
7 Correct 1326 ms 5412 KB Output is correct
8 Correct 1320 ms 5404 KB Output is correct
9 Correct 1331 ms 5232 KB Output is correct
10 Correct 1329 ms 5360 KB Output is correct
11 Correct 1324 ms 5392 KB Output is correct
12 Correct 1354 ms 5328 KB Output is correct
13 Correct 1326 ms 5248 KB Output is correct
14 Correct 1336 ms 5256 KB Output is correct
15 Correct 1329 ms 5152 KB Output is correct
16 Correct 237 ms 3828 KB Output is correct
17 Correct 254 ms 3604 KB Output is correct
18 Correct 248 ms 3728 KB Output is correct
19 Correct 263 ms 3672 KB Output is correct
20 Correct 248 ms 3660 KB Output is correct
21 Correct 1989 ms 5568 KB Output is correct
22 Correct 1997 ms 5292 KB Output is correct
23 Correct 1957 ms 5392 KB Output is correct
24 Correct 1998 ms 5388 KB Output is correct
25 Correct 1942 ms 5344 KB Output is correct
26 Correct 1978 ms 5624 KB Output is correct
27 Correct 1996 ms 5272 KB Output is correct
28 Execution timed out 2003 ms 5572 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 972 KB Output is correct
2 Correct 25 ms 1040 KB Output is correct
3 Correct 24 ms 1044 KB Output is correct
4 Correct 26 ms 1000 KB Output is correct
5 Correct 25 ms 1032 KB Output is correct
6 Correct 27 ms 1068 KB Output is correct
7 Correct 26 ms 972 KB Output is correct
8 Correct 27 ms 1008 KB Output is correct
9 Correct 29 ms 972 KB Output is correct
10 Correct 28 ms 1028 KB Output is correct
11 Correct 26 ms 972 KB Output is correct
12 Correct 24 ms 1016 KB Output is correct
13 Correct 25 ms 1084 KB Output is correct
14 Correct 25 ms 1080 KB Output is correct
15 Correct 24 ms 972 KB Output is correct
16 Correct 11 ms 960 KB Output is correct
17 Correct 11 ms 972 KB Output is correct
18 Correct 11 ms 980 KB Output is correct
19 Correct 11 ms 972 KB Output is correct
20 Correct 12 ms 972 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1377 ms 5328 KB Output is correct
2 Correct 1400 ms 5456 KB Output is correct
3 Correct 1386 ms 5212 KB Output is correct
4 Correct 1353 ms 5180 KB Output is correct
5 Correct 1365 ms 5336 KB Output is correct
6 Correct 1344 ms 5280 KB Output is correct
7 Correct 1326 ms 5412 KB Output is correct
8 Correct 1320 ms 5404 KB Output is correct
9 Correct 1331 ms 5232 KB Output is correct
10 Correct 1329 ms 5360 KB Output is correct
11 Correct 1324 ms 5392 KB Output is correct
12 Correct 1354 ms 5328 KB Output is correct
13 Correct 1326 ms 5248 KB Output is correct
14 Correct 1336 ms 5256 KB Output is correct
15 Correct 1329 ms 5152 KB Output is correct
16 Correct 237 ms 3828 KB Output is correct
17 Correct 254 ms 3604 KB Output is correct
18 Correct 248 ms 3728 KB Output is correct
19 Correct 263 ms 3672 KB Output is correct
20 Correct 248 ms 3660 KB Output is correct
21 Correct 1989 ms 5568 KB Output is correct
22 Correct 1997 ms 5292 KB Output is correct
23 Correct 1957 ms 5392 KB Output is correct
24 Correct 1998 ms 5388 KB Output is correct
25 Correct 1942 ms 5344 KB Output is correct
26 Correct 1978 ms 5624 KB Output is correct
27 Correct 1996 ms 5272 KB Output is correct
28 Execution timed out 2003 ms 5572 KB Time limit exceeded
29 Halted 0 ms 0 KB -