oj.uz

Submission #499669

# Submission time Handle Problem Language Result Execution time Memory
499669 2021-12-29T08:10:34 Z keta_tsimakuridze Boat (APIO16_boat) C++14
36 / 100
 1979 ms 8312 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][3 *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 1282 ms 8200 KB Output is correct
2 Correct 1286 ms 8284 KB Output is correct
3 Correct 1266 ms 8184 KB Output is correct
4 Correct 1252 ms 8136 KB Output is correct
5 Correct 1275 ms 8196 KB Output is correct
6 Correct 1254 ms 8216 KB Output is correct
7 Correct 1297 ms 8312 KB Output is correct
8 Correct 1282 ms 8136 KB Output is correct
9 Correct 1274 ms 8248 KB Output is correct
10 Correct 1360 ms 8180 KB Output is correct
11 Correct 1300 ms 8196 KB Output is correct
12 Correct 1280 ms 8160 KB Output is correct
13 Correct 1305 ms 8160 KB Output is correct
14 Correct 1269 ms 8164 KB Output is correct
15 Correct 1297 ms 8280 KB Output is correct
16 Correct 221 ms 4988 KB Output is correct
17 Correct 243 ms 4916 KB Output is correct
18 Correct 240 ms 4944 KB Output is correct
19 Correct 243 ms 5144 KB Output is correct
20 Correct 236 ms 4932 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1282 ms 8200 KB Output is correct
2 Correct 1286 ms 8284 KB Output is correct
3 Correct 1266 ms 8184 KB Output is correct
4 Correct 1252 ms 8136 KB Output is correct
5 Correct 1275 ms 8196 KB Output is correct
6 Correct 1254 ms 8216 KB Output is correct
7 Correct 1297 ms 8312 KB Output is correct
8 Correct 1282 ms 8136 KB Output is correct
9 Correct 1274 ms 8248 KB Output is correct
10 Correct 1360 ms 8180 KB Output is correct
11 Correct 1300 ms 8196 KB Output is correct
12 Correct 1280 ms 8160 KB Output is correct
13 Correct 1305 ms 8160 KB Output is correct
14 Correct 1269 ms 8164 KB Output is correct
15 Correct 1297 ms 8280 KB Output is correct
16 Correct 221 ms 4988 KB Output is correct
17 Correct 243 ms 4916 KB Output is correct
18 Correct 240 ms 4944 KB Output is correct
19 Correct 243 ms 5144 KB Output is correct
20 Correct 236 ms 4932 KB Output is correct
21 Incorrect 1979 ms 8284 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1356 KB Output is correct
2 Correct 25 ms 1344 KB Output is correct
3 Correct 27 ms 1408 KB Output is correct
4 Correct 26 ms 1368 KB Output is correct
5 Correct 25 ms 1400 KB Output is correct
6 Correct 26 ms 1328 KB Output is correct
7 Correct 27 ms 1364 KB Output is correct
8 Correct 27 ms 1356 KB Output is correct
9 Correct 33 ms 1396 KB Output is correct
10 Correct 29 ms 1408 KB Output is correct
11 Correct 29 ms 1336 KB Output is correct
12 Correct 24 ms 1380 KB Output is correct
13 Correct 27 ms 1368 KB Output is correct
14 Correct 30 ms 1348 KB Output is correct
15 Correct 27 ms 1428 KB Output is correct
16 Correct 11 ms 1180 KB Output is correct
17 Correct 11 ms 1228 KB Output is correct
18 Correct 12 ms 1200 KB Output is correct
19 Correct 11 ms 1176 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 1282 ms 8200 KB Output is correct
2 Correct 1286 ms 8284 KB Output is correct
3 Correct 1266 ms 8184 KB Output is correct
4 Correct 1252 ms 8136 KB Output is correct
5 Correct 1275 ms 8196 KB Output is correct
6 Correct 1254 ms 8216 KB Output is correct
7 Correct 1297 ms 8312 KB Output is correct
8 Correct 1282 ms 8136 KB Output is correct
9 Correct 1274 ms 8248 KB Output is correct
10 Correct 1360 ms 8180 KB Output is correct
11 Correct 1300 ms 8196 KB Output is correct
12 Correct 1280 ms 8160 KB Output is correct
13 Correct 1305 ms 8160 KB Output is correct
14 Correct 1269 ms 8164 KB Output is correct
15 Correct 1297 ms 8280 KB Output is correct
16 Correct 221 ms 4988 KB Output is correct
17 Correct 243 ms 4916 KB Output is correct
18 Correct 240 ms 4944 KB Output is correct
19 Correct 243 ms 5144 KB Output is correct
20 Correct 236 ms 4932 KB Output is correct
21 Incorrect 1979 ms 8284 KB Output isn't correct
22 Halted 0 ms 0 KB -