oj.uz

Submission #499670

# Submission time Handle Problem Language Result Execution time Memory
499670 2021-12-29T08:11:48 Z keta_tsimakuridze Boat (APIO16_boat) C++14
36 / 100
 2000 ms 10484 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][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 = 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 8296 KB Output is correct
2 Correct 1269 ms 8308 KB Output is correct
3 Correct 1254 ms 8132 KB Output is correct
4 Correct 1265 ms 8164 KB Output is correct
5 Correct 1254 ms 8336 KB Output is correct
6 Correct 1239 ms 8472 KB Output is correct
7 Correct 1236 ms 8404 KB Output is correct
8 Correct 1239 ms 8208 KB Output is correct
9 Correct 1239 ms 8160 KB Output is correct
10 Correct 1251 ms 8252 KB Output is correct
11 Correct 1228 ms 8312 KB Output is correct
12 Correct 1231 ms 8384 KB Output is correct
13 Correct 1238 ms 8192 KB Output is correct
14 Correct 1240 ms 8344 KB Output is correct
15 Correct 1238 ms 8428 KB Output is correct
16 Correct 228 ms 5044 KB Output is correct
17 Correct 241 ms 4996 KB Output is correct
18 Correct 230 ms 5012 KB Output is correct
19 Correct 243 ms 5000 KB Output is correct
20 Correct 230 ms 4912 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 8296 KB Output is correct
2 Correct 1269 ms 8308 KB Output is correct
3 Correct 1254 ms 8132 KB Output is correct
4 Correct 1265 ms 8164 KB Output is correct
5 Correct 1254 ms 8336 KB Output is correct
6 Correct 1239 ms 8472 KB Output is correct
7 Correct 1236 ms 8404 KB Output is correct
8 Correct 1239 ms 8208 KB Output is correct
9 Correct 1239 ms 8160 KB Output is correct
10 Correct 1251 ms 8252 KB Output is correct
11 Correct 1228 ms 8312 KB Output is correct
12 Correct 1231 ms 8384 KB Output is correct
13 Correct 1238 ms 8192 KB Output is correct
14 Correct 1240 ms 8344 KB Output is correct
15 Correct 1238 ms 8428 KB Output is correct
16 Correct 228 ms 5044 KB Output is correct
17 Correct 241 ms 4996 KB Output is correct
18 Correct 230 ms 5012 KB Output is correct
19 Correct 243 ms 5000 KB Output is correct
20 Correct 230 ms 4912 KB Output is correct
21 Correct 1924 ms 10412 KB Output is correct
22 Correct 1965 ms 10260 KB Output is correct
23 Correct 1873 ms 10484 KB Output is correct
24 Correct 1914 ms 10288 KB Output is correct
25 Correct 1886 ms 10392 KB Output is correct
26 Correct 1948 ms 10316 KB Output is correct
27 Correct 1960 ms 10324 KB Output is correct
28 Correct 1956 ms 10228 KB Output is correct
29 Correct 1948 ms 10316 KB Output is correct
30 Execution timed out 2068 ms 10316 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1356 KB Output is correct
2 Correct 26 ms 1352 KB Output is correct
3 Correct 24 ms 1348 KB Output is correct
4 Correct 24 ms 1356 KB Output is correct
5 Correct 27 ms 1352 KB Output is correct
6 Correct 26 ms 1324 KB Output is correct
7 Correct 25 ms 1352 KB Output is correct
8 Correct 26 ms 1368 KB Output is correct
9 Correct 26 ms 1356 KB Output is correct
10 Correct 29 ms 1372 KB Output is correct
11 Correct 25 ms 1384 KB Output is correct
12 Correct 23 ms 1412 KB Output is correct
13 Correct 23 ms 1388 KB Output is correct
14 Correct 24 ms 1384 KB Output is correct
15 Correct 24 ms 1368 KB Output is correct
16 Correct 11 ms 1228 KB Output is correct
17 Correct 11 ms 1228 KB Output is correct
18 Correct 11 ms 1228 KB Output is correct
19 Correct 12 ms 1228 KB Output is correct
20 Correct 12 ms 1228 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 8296 KB Output is correct
2 Correct 1269 ms 8308 KB Output is correct
3 Correct 1254 ms 8132 KB Output is correct
4 Correct 1265 ms 8164 KB Output is correct
5 Correct 1254 ms 8336 KB Output is correct
6 Correct 1239 ms 8472 KB Output is correct
7 Correct 1236 ms 8404 KB Output is correct
8 Correct 1239 ms 8208 KB Output is correct
9 Correct 1239 ms 8160 KB Output is correct
10 Correct 1251 ms 8252 KB Output is correct
11 Correct 1228 ms 8312 KB Output is correct
12 Correct 1231 ms 8384 KB Output is correct
13 Correct 1238 ms 8192 KB Output is correct
14 Correct 1240 ms 8344 KB Output is correct
15 Correct 1238 ms 8428 KB Output is correct
16 Correct 228 ms 5044 KB Output is correct
17 Correct 241 ms 4996 KB Output is correct
18 Correct 230 ms 5012 KB Output is correct
19 Correct 243 ms 5000 KB Output is correct
20 Correct 230 ms 4912 KB Output is correct
21 Correct 1924 ms 10412 KB Output is correct
22 Correct 1965 ms 10260 KB Output is correct
23 Correct 1873 ms 10484 KB Output is correct
24 Correct 1914 ms 10288 KB Output is correct
25 Correct 1886 ms 10392 KB Output is correct
26 Correct 1948 ms 10316 KB Output is correct
27 Correct 1960 ms 10324 KB Output is correct
28 Correct 1956 ms 10228 KB Output is correct
29 Correct 1948 ms 10316 KB Output is correct
30 Execution timed out 2068 ms 10316 KB Time limit exceeded
31 Halted 0 ms 0 KB -