oj.uz

Submission #499668

# Submission time Handle Problem Language Result Execution time Memory
499668 2021-12-29T08:06:58 Z keta_tsimakuridze Boat (APIO16_boat) C++14
36 / 100
 1895 ms 6532 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][2 *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 1267 ms 6252 KB Output is correct
2 Correct 1254 ms 6264 KB Output is correct
3 Correct 1235 ms 6264 KB Output is correct
4 Correct 1225 ms 6340 KB Output is correct
5 Correct 1231 ms 6240 KB Output is correct
6 Correct 1258 ms 6368 KB Output is correct
7 Correct 1250 ms 6340 KB Output is correct
8 Correct 1245 ms 6280 KB Output is correct
9 Correct 1242 ms 6260 KB Output is correct
10 Correct 1239 ms 6368 KB Output is correct
11 Correct 1240 ms 6472 KB Output is correct
12 Correct 1242 ms 6344 KB Output is correct
13 Correct 1238 ms 6340 KB Output is correct
14 Correct 1238 ms 6268 KB Output is correct
15 Correct 1247 ms 6328 KB Output is correct
16 Correct 220 ms 4976 KB Output is correct
17 Correct 238 ms 4932 KB Output is correct
18 Correct 231 ms 5116 KB Output is correct
19 Correct 240 ms 4988 KB Output is correct
20 Correct 238 ms 5004 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1267 ms 6252 KB Output is correct
2 Correct 1254 ms 6264 KB Output is correct
3 Correct 1235 ms 6264 KB Output is correct
4 Correct 1225 ms 6340 KB Output is correct
5 Correct 1231 ms 6240 KB Output is correct
6 Correct 1258 ms 6368 KB Output is correct
7 Correct 1250 ms 6340 KB Output is correct
8 Correct 1245 ms 6280 KB Output is correct
9 Correct 1242 ms 6260 KB Output is correct
10 Correct 1239 ms 6368 KB Output is correct
11 Correct 1240 ms 6472 KB Output is correct
12 Correct 1242 ms 6344 KB Output is correct
13 Correct 1238 ms 6340 KB Output is correct
14 Correct 1238 ms 6268 KB Output is correct
15 Correct 1247 ms 6328 KB Output is correct
16 Correct 220 ms 4976 KB Output is correct
17 Correct 238 ms 4932 KB Output is correct
18 Correct 231 ms 5116 KB Output is correct
19 Correct 240 ms 4988 KB Output is correct
20 Correct 238 ms 5004 KB Output is correct
21 Incorrect 1895 ms 6532 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 24 ms 1396 KB Output is correct
2 Correct 24 ms 1356 KB Output is correct
3 Correct 25 ms 1376 KB Output is correct
4 Correct 24 ms 1356 KB Output is correct
5 Correct 24 ms 1356 KB Output is correct
6 Correct 26 ms 1332 KB Output is correct
7 Correct 25 ms 1404 KB Output is correct
8 Correct 26 ms 1348 KB Output is correct
9 Correct 25 ms 1356 KB Output is correct
10 Correct 26 ms 1348 KB Output is correct
11 Correct 24 ms 1336 KB Output is correct
12 Correct 24 ms 1324 KB Output is correct
13 Correct 24 ms 1328 KB Output is correct
14 Correct 24 ms 1408 KB Output is correct
15 Correct 24 ms 1356 KB Output is correct
16 Correct 12 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 10 ms 1264 KB Output is correct
20 Correct 11 ms 1272 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1267 ms 6252 KB Output is correct
2 Correct 1254 ms 6264 KB Output is correct
3 Correct 1235 ms 6264 KB Output is correct
4 Correct 1225 ms 6340 KB Output is correct
5 Correct 1231 ms 6240 KB Output is correct
6 Correct 1258 ms 6368 KB Output is correct
7 Correct 1250 ms 6340 KB Output is correct
8 Correct 1245 ms 6280 KB Output is correct
9 Correct 1242 ms 6260 KB Output is correct
10 Correct 1239 ms 6368 KB Output is correct
11 Correct 1240 ms 6472 KB Output is correct
12 Correct 1242 ms 6344 KB Output is correct
13 Correct 1238 ms 6340 KB Output is correct
14 Correct 1238 ms 6268 KB Output is correct
15 Correct 1247 ms 6328 KB Output is correct
16 Correct 220 ms 4976 KB Output is correct
17 Correct 238 ms 4932 KB Output is correct
18 Correct 231 ms 5116 KB Output is correct
19 Correct 240 ms 4988 KB Output is correct
20 Correct 238 ms 5004 KB Output is correct
21 Incorrect 1895 ms 6532 KB Output isn't correct
22 Halted 0 ms 0 KB -