oj.uz

Submission #554415

# Submission time Handle Problem Language Result Execution time Memory
554415 2022-04-28T10:54:45 Z fatemetmhr Boat (APIO16_boat) C++17
9 / 100
 664 ms 7396 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 637 ms 7388 KB Output is correct
2 Correct 629 ms 7184 KB Output is correct
3 Correct 623 ms 7212 KB Output is correct
4 Correct 646 ms 7340 KB Output is correct
5 Correct 664 ms 7256 KB Output is correct
6 Correct 619 ms 7372 KB Output is correct
7 Correct 633 ms 7308 KB Output is correct
8 Correct 648 ms 7160 KB Output is correct
9 Correct 634 ms 7288 KB Output is correct
10 Correct 650 ms 7220 KB Output is correct
11 Correct 628 ms 7256 KB Output is correct
12 Correct 624 ms 7204 KB Output is correct
13 Correct 617 ms 7260 KB Output is correct
14 Correct 616 ms 7396 KB Output is correct
15 Correct 625 ms 7200 KB Output is correct
16 Correct 116 ms 3916 KB Output is correct
17 Correct 125 ms 3964 KB Output is correct
18 Correct 116 ms 3916 KB Output is correct
19 Correct 122 ms 3976 KB Output is correct
20 Correct 116 ms 4044 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 7388 KB Output is correct
2 Correct 629 ms 7184 KB Output is correct
3 Correct 623 ms 7212 KB Output is correct
4 Correct 646 ms 7340 KB Output is correct
5 Correct 664 ms 7256 KB Output is correct
6 Correct 619 ms 7372 KB Output is correct
7 Correct 633 ms 7308 KB Output is correct
8 Correct 648 ms 7160 KB Output is correct
9 Correct 634 ms 7288 KB Output is correct
10 Correct 650 ms 7220 KB Output is correct
11 Correct 628 ms 7256 KB Output is correct
12 Correct 624 ms 7204 KB Output is correct
13 Correct 617 ms 7260 KB Output is correct
14 Correct 616 ms 7396 KB Output is correct
15 Correct 625 ms 7200 KB Output is correct
16 Correct 116 ms 3916 KB Output is correct
17 Correct 125 ms 3964 KB Output is correct
18 Correct 116 ms 3916 KB Output is correct
19 Correct 122 ms 3976 KB Output is correct
20 Correct 116 ms 4044 KB Output is correct
21 Incorrect 607 ms 6820 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 7388 KB Output is correct
2 Correct 629 ms 7184 KB Output is correct
3 Correct 623 ms 7212 KB Output is correct
4 Correct 646 ms 7340 KB Output is correct
5 Correct 664 ms 7256 KB Output is correct
6 Correct 619 ms 7372 KB Output is correct
7 Correct 633 ms 7308 KB Output is correct
8 Correct 648 ms 7160 KB Output is correct
9 Correct 634 ms 7288 KB Output is correct
10 Correct 650 ms 7220 KB Output is correct
11 Correct 628 ms 7256 KB Output is correct
12 Correct 624 ms 7204 KB Output is correct
13 Correct 617 ms 7260 KB Output is correct
14 Correct 616 ms 7396 KB Output is correct
15 Correct 625 ms 7200 KB Output is correct
16 Correct 116 ms 3916 KB Output is correct
17 Correct 125 ms 3964 KB Output is correct
18 Correct 116 ms 3916 KB Output is correct
19 Correct 122 ms 3976 KB Output is correct
20 Correct 116 ms 4044 KB Output is correct
21 Incorrect 607 ms 6820 KB Output isn't correct
22 Halted 0 ms 0 KB -