oj.uz

Submission #554393

# Submission time Handle Problem Language Result Execution time Memory
554393 2022-04-28T10:37:36 Z fatemetmhr Boat (APIO16_boat) C++17
0 / 100
 640 ms 7404 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]; // (..]
        l[i]--;
        exx.pb(l[i]);
        exx.pb(r[i]);
    }
    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() + 1;
        r[i] = lower_bound(all(exx), r[i]) - exx.begin() + 1;
        //cout << "segment " << i << ' ' << l[i] << ' ' << r[i] << endl;
    }
    for(int i = 1; i < exx.size(); i++)
        szb[i + 1] = exx[i] - exx[i - 1];
    int blsz = exx.size() + 2;

    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;
    }

    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:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 1; i < exx.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 7232 KB Output is correct
2 Correct 640 ms 7244 KB Output is correct
3 Correct 621 ms 7376 KB Output is correct
4 Correct 625 ms 7300 KB Output is correct
5 Correct 613 ms 7304 KB Output is correct
6 Correct 616 ms 7192 KB Output is correct
7 Correct 627 ms 7404 KB Output is correct
8 Correct 622 ms 7356 KB Output is correct
9 Correct 629 ms 7264 KB Output is correct
10 Correct 613 ms 7304 KB Output is correct
11 Correct 620 ms 7312 KB Output is correct
12 Correct 617 ms 7252 KB Output is correct
13 Correct 627 ms 7276 KB Output is correct
14 Correct 614 ms 7228 KB Output is correct
15 Correct 621 ms 7364 KB Output is correct
16 Incorrect 111 ms 3904 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 7232 KB Output is correct
2 Correct 640 ms 7244 KB Output is correct
3 Correct 621 ms 7376 KB Output is correct
4 Correct 625 ms 7300 KB Output is correct
5 Correct 613 ms 7304 KB Output is correct
6 Correct 616 ms 7192 KB Output is correct
7 Correct 627 ms 7404 KB Output is correct
8 Correct 622 ms 7356 KB Output is correct
9 Correct 629 ms 7264 KB Output is correct
10 Correct 613 ms 7304 KB Output is correct
11 Correct 620 ms 7312 KB Output is correct
12 Correct 617 ms 7252 KB Output is correct
13 Correct 627 ms 7276 KB Output is correct
14 Correct 614 ms 7228 KB Output is correct
15 Correct 621 ms 7364 KB Output is correct
16 Incorrect 111 ms 3904 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 2544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 7232 KB Output is correct
2 Correct 640 ms 7244 KB Output is correct
3 Correct 621 ms 7376 KB Output is correct
4 Correct 625 ms 7300 KB Output is correct
5 Correct 613 ms 7304 KB Output is correct
6 Correct 616 ms 7192 KB Output is correct
7 Correct 627 ms 7404 KB Output is correct
8 Correct 622 ms 7356 KB Output is correct
9 Correct 629 ms 7264 KB Output is correct
10 Correct 613 ms 7304 KB Output is correct
11 Correct 620 ms 7312 KB Output is correct
12 Correct 617 ms 7252 KB Output is correct
13 Correct 627 ms 7276 KB Output is correct
14 Correct 614 ms 7228 KB Output is correct
15 Correct 621 ms 7364 KB Output is correct
16 Incorrect 111 ms 3904 KB Output isn't correct
17 Halted 0 ms 0 KB -