oj.uz

Submission #554412

# Submission time Handle Problem Language Result Execution time Memory
554412 2022-04-28T10:52:29 Z fatemetmhr Boat (APIO16_boat) C++17
0 / 100
 619 ms 7460 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;
                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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 7272 KB Output is correct
2 Correct 603 ms 7304 KB Output is correct
3 Correct 601 ms 7184 KB Output is correct
4 Correct 613 ms 7460 KB Output is correct
5 Correct 607 ms 7184 KB Output is correct
6 Correct 605 ms 7232 KB Output is correct
7 Correct 604 ms 7292 KB Output is correct
8 Correct 616 ms 7208 KB Output is correct
9 Correct 610 ms 7368 KB Output is correct
10 Correct 616 ms 7232 KB Output is correct
11 Correct 617 ms 7404 KB Output is correct
12 Correct 619 ms 7280 KB Output is correct
13 Correct 607 ms 7264 KB Output is correct
14 Correct 604 ms 7240 KB Output is correct
15 Correct 613 ms 7392 KB Output is correct
16 Incorrect 111 ms 3908 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 7272 KB Output is correct
2 Correct 603 ms 7304 KB Output is correct
3 Correct 601 ms 7184 KB Output is correct
4 Correct 613 ms 7460 KB Output is correct
5 Correct 607 ms 7184 KB Output is correct
6 Correct 605 ms 7232 KB Output is correct
7 Correct 604 ms 7292 KB Output is correct
8 Correct 616 ms 7208 KB Output is correct
9 Correct 610 ms 7368 KB Output is correct
10 Correct 616 ms 7232 KB Output is correct
11 Correct 617 ms 7404 KB Output is correct
12 Correct 619 ms 7280 KB Output is correct
13 Correct 607 ms 7264 KB Output is correct
14 Correct 604 ms 7240 KB Output is correct
15 Correct 613 ms 7392 KB Output is correct
16 Incorrect 111 ms 3908 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 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 613 ms 7272 KB Output is correct
2 Correct 603 ms 7304 KB Output is correct
3 Correct 601 ms 7184 KB Output is correct
4 Correct 613 ms 7460 KB Output is correct
5 Correct 607 ms 7184 KB Output is correct
6 Correct 605 ms 7232 KB Output is correct
7 Correct 604 ms 7292 KB Output is correct
8 Correct 616 ms 7208 KB Output is correct
9 Correct 610 ms 7368 KB Output is correct
10 Correct 616 ms 7232 KB Output is correct
11 Correct 617 ms 7404 KB Output is correct
12 Correct 619 ms 7280 KB Output is correct
13 Correct 607 ms 7264 KB Output is correct
14 Correct 604 ms 7240 KB Output is correct
15 Correct 613 ms 7392 KB Output is correct
16 Incorrect 111 ms 3908 KB Output isn't correct
17 Halted 0 ms 0 KB -