oj.uz

Submission #500511

# Submission time Handle Problem Language Result Execution time Memory
500511 2021-12-31T09:30:01 Z doowey Boat (APIO16_boat) C++14
58 / 100
 2000 ms 12792 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 505;
const int M = N * 4;
const int MOD = (int)1e9 + 7;
int L[N], R[N];

int C[M][N];
int I[N][N];

int fin[M][N];

int powr(int n, int k){
    if(k == 0) return 1;
    int p = powr(n, k / 2);
    p = (p * 1ll * p) % MOD;
    if(k % 2 == 1) p = (p * 1ll * n) % MOD;
    return p;
}

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
    else if(a < 0) a += MOD;
}

int dp[N][M];
int dif[N];


int main(){
    fastIO;
    int n;
    cin >> n;
    vector<int> pp;
    for(int i = 1; i <= n; i ++ ){
        cin >> L[i] >> R[i];
        pp.push_back(L[i]);
        pp.push_back(R[i]);
    }
    sort(pp.begin(), pp.end());
    pp.resize(unique(pp.begin(), pp.end()) - pp.begin());
    vector<pii> segm;
    for(int i = 0 ; i < pp.size(); i ++ ){
        segm.push_back(mp(pp[i], pp[i]));
        if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
            segm.push_back(mp(pp[i] + 1, pp[i + 1] - 1));
        }
    }
    int m = segm.size();
    for(int i = 0; i < N ;i ++ ){
        I[i][0] = 1;
    }
    for(int k = 1; k < N ; k ++ ){
        for(int i = 1; i < N ; i ++ ){
            add(I[i][k], I[i-1][k]);
            add(I[i][k], I[i-1][k-1]);
        }
    }
    int sz;
    int P, Q;
    int inv;
    int cum;
    for(int i = 0 ; i < m ; i ++ ){
        sz = segm[i].se - segm[i].fi + 1;
        P = Q = 1;
        for(int j = 1; j <= n; j ++ ){
            if(j > sz) break;
            P = (P * 1ll * (sz - j + 1)) % MOD;
            Q = (Q * 1ll * j) % MOD;
            inv = powr(Q, MOD - 2);
            C[i][j] = (P * 1ll * inv) % MOD;
        }
        for(int j = 1; j <= n; j ++ ){
            for(int v = 1; v <= j; v ++ ){
                add(fin[i][j], (C[i][v] * 1ll * I[j][v]) % MOD);
            }
        }
        for(int j = n; j >= 1; j -- ){
            add(fin[i][j], -fin[i][j-1]);
        }
    }
    int tl, tr;
    int mm;
    int side;
    int res = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            tl = segm[j].fi;
            tr = segm[j].se;
            if(L[i] <= tl && tr <= R[i]){
                mm = 0;
                for(int v = i; v >= 1; v -- ){

                    if(L[v] <= tl && tr <= R[v]) mm ++ ;
                    side = 0;
                    if(j > 0) add(side, dp[v - 1][j - 1]);
                    if(v == 1) add(side, 1);
                    add(dp[i][j], (side * 1ll * fin[j][mm]) % MOD);
                }
            }
            add(res, dp[i][j]);
            if(j)
                add(dp[i][j], dp[i][j-1]);
        }
    }

    cout << res << "\n";
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0 ; i < pp.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
boat.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
      |            ~~~~~~^~~~~~~~~~~
boat.cpp:73:9: warning: unused variable 'cum' [-Wunused-variable]
   73 |     int cum;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 9204 KB Output is correct
2 Correct 641 ms 9228 KB Output is correct
3 Correct 679 ms 9140 KB Output is correct
4 Correct 640 ms 9208 KB Output is correct
5 Correct 642 ms 9132 KB Output is correct
6 Correct 655 ms 9152 KB Output is correct
7 Correct 636 ms 9296 KB Output is correct
8 Correct 633 ms 9232 KB Output is correct
9 Correct 640 ms 9244 KB Output is correct
10 Correct 638 ms 9212 KB Output is correct
11 Correct 642 ms 9292 KB Output is correct
12 Correct 641 ms 9244 KB Output is correct
13 Correct 636 ms 9268 KB Output is correct
14 Correct 635 ms 9148 KB Output is correct
15 Correct 639 ms 9232 KB Output is correct
16 Correct 122 ms 4340 KB Output is correct
17 Correct 125 ms 4368 KB Output is correct
18 Correct 121 ms 4360 KB Output is correct
19 Correct 125 ms 4420 KB Output is correct
20 Correct 136 ms 4384 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 9204 KB Output is correct
2 Correct 641 ms 9228 KB Output is correct
3 Correct 679 ms 9140 KB Output is correct
4 Correct 640 ms 9208 KB Output is correct
5 Correct 642 ms 9132 KB Output is correct
6 Correct 655 ms 9152 KB Output is correct
7 Correct 636 ms 9296 KB Output is correct
8 Correct 633 ms 9232 KB Output is correct
9 Correct 640 ms 9244 KB Output is correct
10 Correct 638 ms 9212 KB Output is correct
11 Correct 642 ms 9292 KB Output is correct
12 Correct 641 ms 9244 KB Output is correct
13 Correct 636 ms 9268 KB Output is correct
14 Correct 635 ms 9148 KB Output is correct
15 Correct 639 ms 9232 KB Output is correct
16 Correct 122 ms 4340 KB Output is correct
17 Correct 125 ms 4368 KB Output is correct
18 Correct 121 ms 4360 KB Output is correct
19 Correct 125 ms 4420 KB Output is correct
20 Correct 136 ms 4384 KB Output is correct
21 Correct 1403 ms 11880 KB Output is correct
22 Correct 1449 ms 11888 KB Output is correct
23 Correct 1242 ms 11820 KB Output is correct
24 Correct 1362 ms 11960 KB Output is correct
25 Correct 1316 ms 11780 KB Output is correct
26 Correct 1424 ms 11696 KB Output is correct
27 Correct 1424 ms 11480 KB Output is correct
28 Correct 1418 ms 11668 KB Output is correct
29 Correct 1444 ms 11476 KB Output is correct
30 Correct 928 ms 12676 KB Output is correct
31 Correct 989 ms 12696 KB Output is correct
32 Correct 930 ms 12596 KB Output is correct
33 Correct 900 ms 12600 KB Output is correct
34 Correct 911 ms 12524 KB Output is correct
35 Correct 606 ms 9248 KB Output is correct
36 Correct 656 ms 9232 KB Output is correct
37 Correct 661 ms 9160 KB Output is correct
38 Correct 621 ms 9252 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3416 KB Output is correct
2 Correct 25 ms 3416 KB Output is correct
3 Correct 23 ms 3384 KB Output is correct
4 Correct 23 ms 3404 KB Output is correct
5 Correct 26 ms 3348 KB Output is correct
6 Correct 26 ms 3356 KB Output is correct
7 Correct 26 ms 3420 KB Output is correct
8 Correct 26 ms 3424 KB Output is correct
9 Correct 26 ms 3380 KB Output is correct
10 Correct 27 ms 3424 KB Output is correct
11 Correct 24 ms 3404 KB Output is correct
12 Correct 23 ms 3376 KB Output is correct
13 Correct 23 ms 3380 KB Output is correct
14 Correct 25 ms 3332 KB Output is correct
15 Correct 26 ms 3320 KB Output is correct
16 Correct 12 ms 2460 KB Output is correct
17 Correct 11 ms 2380 KB Output is correct
18 Correct 12 ms 2364 KB Output is correct
19 Correct 11 ms 2464 KB Output is correct
20 Correct 12 ms 2504 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 9204 KB Output is correct
2 Correct 641 ms 9228 KB Output is correct
3 Correct 679 ms 9140 KB Output is correct
4 Correct 640 ms 9208 KB Output is correct
5 Correct 642 ms 9132 KB Output is correct
6 Correct 655 ms 9152 KB Output is correct
7 Correct 636 ms 9296 KB Output is correct
8 Correct 633 ms 9232 KB Output is correct
9 Correct 640 ms 9244 KB Output is correct
10 Correct 638 ms 9212 KB Output is correct
11 Correct 642 ms 9292 KB Output is correct
12 Correct 641 ms 9244 KB Output is correct
13 Correct 636 ms 9268 KB Output is correct
14 Correct 635 ms 9148 KB Output is correct
15 Correct 639 ms 9232 KB Output is correct
16 Correct 122 ms 4340 KB Output is correct
17 Correct 125 ms 4368 KB Output is correct
18 Correct 121 ms 4360 KB Output is correct
19 Correct 125 ms 4420 KB Output is correct
20 Correct 136 ms 4384 KB Output is correct
21 Correct 1403 ms 11880 KB Output is correct
22 Correct 1449 ms 11888 KB Output is correct
23 Correct 1242 ms 11820 KB Output is correct
24 Correct 1362 ms 11960 KB Output is correct
25 Correct 1316 ms 11780 KB Output is correct
26 Correct 1424 ms 11696 KB Output is correct
27 Correct 1424 ms 11480 KB Output is correct
28 Correct 1418 ms 11668 KB Output is correct
29 Correct 1444 ms 11476 KB Output is correct
30 Correct 928 ms 12676 KB Output is correct
31 Correct 989 ms 12696 KB Output is correct
32 Correct 930 ms 12596 KB Output is correct
33 Correct 900 ms 12600 KB Output is correct
34 Correct 911 ms 12524 KB Output is correct
35 Correct 606 ms 9248 KB Output is correct
36 Correct 656 ms 9232 KB Output is correct
37 Correct 661 ms 9160 KB Output is correct
38 Correct 621 ms 9252 KB Output is correct
39 Correct 25 ms 3416 KB Output is correct
40 Correct 25 ms 3416 KB Output is correct
41 Correct 23 ms 3384 KB Output is correct
42 Correct 23 ms 3404 KB Output is correct
43 Correct 26 ms 3348 KB Output is correct
44 Correct 26 ms 3356 KB Output is correct
45 Correct 26 ms 3420 KB Output is correct
46 Correct 26 ms 3424 KB Output is correct
47 Correct 26 ms 3380 KB Output is correct
48 Correct 27 ms 3424 KB Output is correct
49 Correct 24 ms 3404 KB Output is correct
50 Correct 23 ms 3376 KB Output is correct
51 Correct 23 ms 3380 KB Output is correct
52 Correct 25 ms 3332 KB Output is correct
53 Correct 26 ms 3320 KB Output is correct
54 Correct 12 ms 2460 KB Output is correct
55 Correct 11 ms 2380 KB Output is correct
56 Correct 12 ms 2364 KB Output is correct
57 Correct 11 ms 2464 KB Output is correct
58 Correct 12 ms 2504 KB Output is correct
59 Execution timed out 2073 ms 12792 KB Time limit exceeded
60 Halted 0 ms 0 KB -