oj.uz

Submission #554396

# Submission time Handle Problem Language Result Execution time Memory
554396 2022-04-28T10:39:03 Z fatemetmhr Boat (APIO16_boat) C++17
9 / 100
 623 ms 7324 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;
            continue;
            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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 7264 KB Output is correct
2 Correct 607 ms 7244 KB Output is correct
3 Correct 610 ms 7228 KB Output is correct
4 Correct 619 ms 7172 KB Output is correct
5 Correct 611 ms 7260 KB Output is correct
6 Correct 601 ms 7204 KB Output is correct
7 Correct 610 ms 7204 KB Output is correct
8 Correct 623 ms 7196 KB Output is correct
9 Correct 620 ms 7316 KB Output is correct
10 Correct 611 ms 7220 KB Output is correct
11 Correct 620 ms 7284 KB Output is correct
12 Correct 620 ms 7208 KB Output is correct
13 Correct 613 ms 7324 KB Output is correct
14 Correct 608 ms 7276 KB Output is correct
15 Correct 615 ms 7264 KB Output is correct
16 Correct 110 ms 3912 KB Output is correct
17 Correct 118 ms 4136 KB Output is correct
18 Correct 117 ms 3980 KB Output is correct
19 Correct 117 ms 3980 KB Output is correct
20 Correct 114 ms 4028 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 7264 KB Output is correct
2 Correct 607 ms 7244 KB Output is correct
3 Correct 610 ms 7228 KB Output is correct
4 Correct 619 ms 7172 KB Output is correct
5 Correct 611 ms 7260 KB Output is correct
6 Correct 601 ms 7204 KB Output is correct
7 Correct 610 ms 7204 KB Output is correct
8 Correct 623 ms 7196 KB Output is correct
9 Correct 620 ms 7316 KB Output is correct
10 Correct 611 ms 7220 KB Output is correct
11 Correct 620 ms 7284 KB Output is correct
12 Correct 620 ms 7208 KB Output is correct
13 Correct 613 ms 7324 KB Output is correct
14 Correct 608 ms 7276 KB Output is correct
15 Correct 615 ms 7264 KB Output is correct
16 Correct 110 ms 3912 KB Output is correct
17 Correct 118 ms 4136 KB Output is correct
18 Correct 117 ms 3980 KB Output is correct
19 Correct 117 ms 3980 KB Output is correct
20 Correct 114 ms 4028 KB Output is correct
21 Incorrect 325 ms 7060 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 7264 KB Output is correct
2 Correct 607 ms 7244 KB Output is correct
3 Correct 610 ms 7228 KB Output is correct
4 Correct 619 ms 7172 KB Output is correct
5 Correct 611 ms 7260 KB Output is correct
6 Correct 601 ms 7204 KB Output is correct
7 Correct 610 ms 7204 KB Output is correct
8 Correct 623 ms 7196 KB Output is correct
9 Correct 620 ms 7316 KB Output is correct
10 Correct 611 ms 7220 KB Output is correct
11 Correct 620 ms 7284 KB Output is correct
12 Correct 620 ms 7208 KB Output is correct
13 Correct 613 ms 7324 KB Output is correct
14 Correct 608 ms 7276 KB Output is correct
15 Correct 615 ms 7264 KB Output is correct
16 Correct 110 ms 3912 KB Output is correct
17 Correct 118 ms 4136 KB Output is correct
18 Correct 117 ms 3980 KB Output is correct
19 Correct 117 ms 3980 KB Output is correct
20 Correct 114 ms 4028 KB Output is correct
21 Incorrect 325 ms 7060 KB Output isn't correct
22 Halted 0 ms 0 KB -