oj.uz

Submission #554408

# Submission time Handle Problem Language Result Execution time Memory
554408 2022-04-28T10:49:47 Z fatemetmhr Boat (APIO16_boat) C++17
0 / 100
 664 ms 7372 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)     x.begin(), x.end()
#define fi         first
#define se         second
#define pb         push_back

const int maxn5 = 5e2 + 5;
const int maxnb = 1e3 + 10;
const int mod   = 1e9 + 7;

int ent[maxn5][maxn5], val[maxnb][maxn5];
int ent2[maxnb][maxn5], szb[maxnb];
int l[maxn5], r[maxn5], ansel[maxn5][maxnb];
int ansbl[maxnb];
vector <int> exx;

inline ll pw(ll a, ll b){
    ll ret = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b&1) ret = ret * a % mod;
    return ret;
}

inline ll entof(ll n, ll r){
    ll s = 1, m = 1;
    for(int i = 0; i < r; i++){
        s = s * (n - i) % mod;
        m = m * (i + 1) % mod;
    }
    return (s * pw(m, mod - 2)) % mod;
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);


    int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> r[i]; // (..]
        r[i]++;
        exx.pb(l[i]);
        exx.pb(r[i]);
    }
    exx.pb(0);
    sort(all(exx));
    exx.resize(unique(all(exx)) - exx.begin());
    for(int i = 0; i < n; i++){
        l[i] = lower_bound(all(exx), l[i]) - exx.begin();
        r[i] = lower_bound(all(exx), r[i]) - exx.begin();
        //cout << "segment " << i << ' ' << l[i] << ' ' << r[i] << endl;
    }
    for(int i = 1; i < exx.size(); i++){
        szb[i] = exx[i] - exx[i - 1];
        //cout << "a bl of " << exx[i] << ' ' << exx[i - 1] << ' ' << szb[i + 1] << endl;
    }
    int blsz = exx.size();

    ent[0][0] = 1;
    for(int i = 1; i < maxn5; i++){
        ent[i][0] = 1;
        for(int j = 1; j <= i; j++)
            ent[i][j] = (ent[i - 1][j - 1] + ent[i - 1][j]) % mod;
    }
    
    for(int i = 1; i < blsz; i++) for(int j = 0; j < maxn5 && j <= szb[i]; j++){
        ent2[i][j] = entof(szb[i], j);
    }


    for(int i = 1; i < blsz; i++) for(int j = 0; j < n; j++){ // bl e i om hast va j nafar davtalab
        // val[i][j] = SIGMA z : C(sz[i], z + 1) * C(j, z);
        for(int z = 0; z + 1 <= szb[i] && z <= j; z++)
            val[i][j] = (val[i][j] + ll(ent2[i][z + 1]) * ent[j][z]) % mod;
        assert(val[i][j] <= 1 || szb[i] > 1);
    }

    ansbl[0] = 1;
    for(int i = 0; i < n; i++){
        for(int j = l[i] + 1; j <= r[i]; j++){
            for(int k = 0; k < j; k++)
                ansel[i][j] = (ansel[i][j] + ansbl[k] * ll(szb[j])) % mod;
            if(i == 0)
                continue;
            int num = l[i - 1] < j && j <= r[i - 1];
            for(int k = i - 2; k >= 0; k--){
                //cout << "aha " << i << ' ' << j << ' ' << k << ' ' << num << ' ' << ansel[k][j - 1] << endl;
                if(num)
                    ansel[i][j] = (ansel[i][j] + ll(ansel[k][j - 1]) * val[j][num]) % mod;
                num += l[k] < j && j <= r[k];
            }
        }
        for(int j = l[i] + 1; j <= r[i]; j++){
            ansbl[j] = (ansbl[j] + ansel[i][j]) % mod;
            //cout << i << ' ' << j << ' ' << ansel[i][j] << endl;
        }
        for(int j = 1; j < blsz; j++)
            ansel[i][j] = (ansel[i][j - 1] + ansel[i][j]) % mod;
    }
    ll out = 0;
    for(int i = 1; i < blsz; i++)
        out += ansbl[i];
    cout << out % mod << endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 1; i < exx.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 7276 KB Output is correct
2 Correct 636 ms 7372 KB Output is correct
3 Correct 623 ms 7256 KB Output is correct
4 Correct 656 ms 7156 KB Output is correct
5 Correct 664 ms 7228 KB Output is correct
6 Correct 658 ms 7152 KB Output is correct
7 Correct 647 ms 7152 KB Output is correct
8 Correct 626 ms 7248 KB Output is correct
9 Correct 618 ms 7292 KB Output is correct
10 Correct 612 ms 7248 KB Output is correct
11 Correct 611 ms 7244 KB Output is correct
12 Correct 609 ms 7276 KB Output is correct
13 Correct 621 ms 7232 KB Output is correct
14 Correct 625 ms 7344 KB Output is correct
15 Correct 624 ms 7204 KB Output is correct
16 Incorrect 110 ms 4116 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 7276 KB Output is correct
2 Correct 636 ms 7372 KB Output is correct
3 Correct 623 ms 7256 KB Output is correct
4 Correct 656 ms 7156 KB Output is correct
5 Correct 664 ms 7228 KB Output is correct
6 Correct 658 ms 7152 KB Output is correct
7 Correct 647 ms 7152 KB Output is correct
8 Correct 626 ms 7248 KB Output is correct
9 Correct 618 ms 7292 KB Output is correct
10 Correct 612 ms 7248 KB Output is correct
11 Correct 611 ms 7244 KB Output is correct
12 Correct 609 ms 7276 KB Output is correct
13 Correct 621 ms 7232 KB Output is correct
14 Correct 625 ms 7344 KB Output is correct
15 Correct 624 ms 7204 KB Output is correct
16 Incorrect 110 ms 4116 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 7276 KB Output is correct
2 Correct 636 ms 7372 KB Output is correct
3 Correct 623 ms 7256 KB Output is correct
4 Correct 656 ms 7156 KB Output is correct
5 Correct 664 ms 7228 KB Output is correct
6 Correct 658 ms 7152 KB Output is correct
7 Correct 647 ms 7152 KB Output is correct
8 Correct 626 ms 7248 KB Output is correct
9 Correct 618 ms 7292 KB Output is correct
10 Correct 612 ms 7248 KB Output is correct
11 Correct 611 ms 7244 KB Output is correct
12 Correct 609 ms 7276 KB Output is correct
13 Correct 621 ms 7232 KB Output is correct
14 Correct 625 ms 7344 KB Output is correct
15 Correct 624 ms 7204 KB Output is correct
16 Incorrect 110 ms 4116 KB Output isn't correct
17 Halted 0 ms 0 KB -