oj.uz

Submission #500518

# Submission time Handle Problem Language Result Execution time Memory
500518 2021-12-31T09:39:35 Z doowey Boat (APIO16_boat) C++14
36 / 100
 504 ms 11812 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 S[N];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    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;
        }
        if(sz == 1){
            for(int j = 1; j <= n; j ++ ){
                fin[i][j] = j;
            }
        }
        else{
            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]){
                if(tl == tr){
                    if(j) add(dp[i][j], S[j-1]);
                    add(dp[i][j], +1);
                }
                else{
                    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]);
        }
        for(int j = 0 ; j < m ; j ++ ){
            add(S[j],dp[i][j]);
        }
    }

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

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 9156 KB Output is correct
2 Correct 454 ms 9156 KB Output is correct
3 Correct 462 ms 9164 KB Output is correct
4 Correct 460 ms 9228 KB Output is correct
5 Correct 473 ms 9188 KB Output is correct
6 Correct 460 ms 9264 KB Output is correct
7 Correct 456 ms 9168 KB Output is correct
8 Correct 462 ms 9124 KB Output is correct
9 Correct 457 ms 9116 KB Output is correct
10 Correct 462 ms 9188 KB Output is correct
11 Correct 461 ms 9200 KB Output is correct
12 Correct 455 ms 9324 KB Output is correct
13 Correct 456 ms 9188 KB Output is correct
14 Correct 456 ms 9196 KB Output is correct
15 Correct 462 ms 9336 KB Output is correct
16 Correct 83 ms 4252 KB Output is correct
17 Correct 89 ms 4348 KB Output is correct
18 Correct 86 ms 4308 KB Output is correct
19 Correct 89 ms 4400 KB Output is correct
20 Correct 89 ms 4420 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 9156 KB Output is correct
2 Correct 454 ms 9156 KB Output is correct
3 Correct 462 ms 9164 KB Output is correct
4 Correct 460 ms 9228 KB Output is correct
5 Correct 473 ms 9188 KB Output is correct
6 Correct 460 ms 9264 KB Output is correct
7 Correct 456 ms 9168 KB Output is correct
8 Correct 462 ms 9124 KB Output is correct
9 Correct 457 ms 9116 KB Output is correct
10 Correct 462 ms 9188 KB Output is correct
11 Correct 461 ms 9200 KB Output is correct
12 Correct 455 ms 9324 KB Output is correct
13 Correct 456 ms 9188 KB Output is correct
14 Correct 456 ms 9196 KB Output is correct
15 Correct 462 ms 9336 KB Output is correct
16 Correct 83 ms 4252 KB Output is correct
17 Correct 89 ms 4348 KB Output is correct
18 Correct 86 ms 4308 KB Output is correct
19 Correct 89 ms 4400 KB Output is correct
20 Correct 89 ms 4420 KB Output is correct
21 Incorrect 504 ms 11812 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 19 ms 3532 KB Output is correct
2 Correct 17 ms 3412 KB Output is correct
3 Correct 17 ms 3416 KB Output is correct
4 Correct 18 ms 3404 KB Output is correct
5 Correct 17 ms 3404 KB Output is correct
6 Correct 19 ms 3380 KB Output is correct
7 Correct 19 ms 3404 KB Output is correct
8 Correct 22 ms 3464 KB Output is correct
9 Correct 18 ms 3404 KB Output is correct
10 Correct 20 ms 3404 KB Output is correct
11 Correct 18 ms 3452 KB Output is correct
12 Correct 17 ms 3420 KB Output is correct
13 Correct 17 ms 3380 KB Output is correct
14 Correct 19 ms 3416 KB Output is correct
15 Correct 17 ms 3464 KB Output is correct
16 Correct 9 ms 2452 KB Output is correct
17 Correct 9 ms 2436 KB Output is correct
18 Correct 9 ms 2472 KB Output is correct
19 Correct 9 ms 2380 KB Output is correct
20 Correct 12 ms 2608 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 9156 KB Output is correct
2 Correct 454 ms 9156 KB Output is correct
3 Correct 462 ms 9164 KB Output is correct
4 Correct 460 ms 9228 KB Output is correct
5 Correct 473 ms 9188 KB Output is correct
6 Correct 460 ms 9264 KB Output is correct
7 Correct 456 ms 9168 KB Output is correct
8 Correct 462 ms 9124 KB Output is correct
9 Correct 457 ms 9116 KB Output is correct
10 Correct 462 ms 9188 KB Output is correct
11 Correct 461 ms 9200 KB Output is correct
12 Correct 455 ms 9324 KB Output is correct
13 Correct 456 ms 9188 KB Output is correct
14 Correct 456 ms 9196 KB Output is correct
15 Correct 462 ms 9336 KB Output is correct
16 Correct 83 ms 4252 KB Output is correct
17 Correct 89 ms 4348 KB Output is correct
18 Correct 86 ms 4308 KB Output is correct
19 Correct 89 ms 4400 KB Output is correct
20 Correct 89 ms 4420 KB Output is correct
21 Incorrect 504 ms 11812 KB Output isn't correct
22 Halted 0 ms 0 KB -