oj.uz

Submission #554414

# Submission time Handle Problem Language Result Execution time Memory
554414 2022-04-28T10:53:55 Z fatemetmhr Boat (APIO16_boat) C++17
9 / 100
 642 ms 9804 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 = 1; 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;
                assert(szb[j] == 1);
                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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 7224 KB Output is correct
2 Correct 634 ms 7248 KB Output is correct
3 Correct 642 ms 7308 KB Output is correct
4 Correct 621 ms 7156 KB Output is correct
5 Correct 613 ms 7244 KB Output is correct
6 Correct 614 ms 7176 KB Output is correct
7 Correct 606 ms 7432 KB Output is correct
8 Correct 609 ms 7188 KB Output is correct
9 Correct 597 ms 7256 KB Output is correct
10 Correct 640 ms 7296 KB Output is correct
11 Correct 610 ms 7384 KB Output is correct
12 Correct 617 ms 7264 KB Output is correct
13 Correct 609 ms 7244 KB Output is correct
14 Correct 614 ms 7348 KB Output is correct
15 Correct 616 ms 7300 KB Output is correct
16 Correct 111 ms 3920 KB Output is correct
17 Correct 116 ms 4052 KB Output is correct
18 Correct 111 ms 3984 KB Output is correct
19 Correct 123 ms 4052 KB Output is correct
20 Correct 115 ms 4024 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 7224 KB Output is correct
2 Correct 634 ms 7248 KB Output is correct
3 Correct 642 ms 7308 KB Output is correct
4 Correct 621 ms 7156 KB Output is correct
5 Correct 613 ms 7244 KB Output is correct
6 Correct 614 ms 7176 KB Output is correct
7 Correct 606 ms 7432 KB Output is correct
8 Correct 609 ms 7188 KB Output is correct
9 Correct 597 ms 7256 KB Output is correct
10 Correct 640 ms 7296 KB Output is correct
11 Correct 610 ms 7384 KB Output is correct
12 Correct 617 ms 7264 KB Output is correct
13 Correct 609 ms 7244 KB Output is correct
14 Correct 614 ms 7348 KB Output is correct
15 Correct 616 ms 7300 KB Output is correct
16 Correct 111 ms 3920 KB Output is correct
17 Correct 116 ms 4052 KB Output is correct
18 Correct 111 ms 3984 KB Output is correct
19 Correct 123 ms 4052 KB Output is correct
20 Correct 115 ms 4024 KB Output is correct
21 Runtime error 18 ms 9804 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 4148 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 7224 KB Output is correct
2 Correct 634 ms 7248 KB Output is correct
3 Correct 642 ms 7308 KB Output is correct
4 Correct 621 ms 7156 KB Output is correct
5 Correct 613 ms 7244 KB Output is correct
6 Correct 614 ms 7176 KB Output is correct
7 Correct 606 ms 7432 KB Output is correct
8 Correct 609 ms 7188 KB Output is correct
9 Correct 597 ms 7256 KB Output is correct
10 Correct 640 ms 7296 KB Output is correct
11 Correct 610 ms 7384 KB Output is correct
12 Correct 617 ms 7264 KB Output is correct
13 Correct 609 ms 7244 KB Output is correct
14 Correct 614 ms 7348 KB Output is correct
15 Correct 616 ms 7300 KB Output is correct
16 Correct 111 ms 3920 KB Output is correct
17 Correct 116 ms 4052 KB Output is correct
18 Correct 111 ms 3984 KB Output is correct
19 Correct 123 ms 4052 KB Output is correct
20 Correct 115 ms 4024 KB Output is correct
21 Runtime error 18 ms 9804 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -