oj.uz

Submission #1078349

# Submission time Handle Problem Language Result Execution time Memory
1078349 2024-08-27T15:43:27 Z underwaterkillerwhale Boat (APIO16_boat) C++17
9 / 100
 362 ms 6996 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e2 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int n, m;
pii a[N];
int dp[N][N * 2], f[N][N * 2], com[N * 2][N], combi[N][N];

inline void add (int &a, int b) { a = a + b; if (a >= Mod) a = a - Mod; }

ll power (int n, int m) {
    if (m == 0) return 1;
    ll t = power (n, m >> 1);
    (t *= t) %= Mod;
    if (m & 1) (t *= n) %= Mod;
    return t;
}

bool cover (pii A, pii B) {
    return A.fs <= B.fs && A.se >= B.se;
}

void solution () {
    cin >> n;
    vector<pii> vec, seg = {MP(0, 0)};
    rep (i, 1, n) {
        cin >> a[i].fs >> a[i].se;
        vec.pb({a[i].fs, 0}), vec.pb({a[i].se, 1});
    }
    sort (ALL(vec));
    vec.resize(unique(ALL(vec)) - vec.begin());
    rep (i, 0, SZ(vec) - 2) {
        if (vec[i].se == vec[i + 1].se) {
            if (vec[i].se == 1) seg.pb({vec[i].fs + 1, vec[i + 1].fs});
            else seg.pb({vec[i].fs, vec[i + 1].fs - 1});
        }
        else if (vec[i].se == 0) seg.pb({vec[i].fs, vec[i + 1].fs});
    }
    m = SZ(seg) - 1;
    rep (i, 0, m) {
        int Len = seg[i].se - seg[i].fs + 1;
        com[i][0] = 1;
        rep (j, 1, n + 1) {
            if (j > Len) com[i][j] = 0;
            else com[i][j] = 1LL * com[i][j - 1] * (Len - j + 1) % Mod * power (j, Mod - 2) % Mod;
//            cout << seg[i].fs <<","<<seg[i].se<<" "<<j<<" "<<com[i][j] <<"\n";
        }
    }
    rep (i, 0, n) {
        rep (j, 0, i) {
            if (j == i || j == 0) combi[i][j] = 1;
            else combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % Mod;
        }
    }
    rep (i, 0, n) {
        rep (j, 0, m) {
            rep (k, 0, i) {
                add(f[i][j], 1LL * combi[i][k] * com[j][k + 1] % Mod);
            }
        }
    }
    rep (j, 0, m) dp[0][j] = 1;
    rep (i, 1, n) {
        dp[i][0] = 1;
        rep (j, 1, m) {
            dp[i][j] = dp[i][j - 1];
            int num = 0;
            reb (k, i, 1) {
                if (cover(a[k], seg[j])) {
                    add(dp[i][j], 1LL * dp[k - 1][j - 1] * f[num][j] % Mod);
                    ++num;
                }
            }
//            cout << i <<" "<<seg[j].fs<<","<<seg[j].se<<": "<<dp[i][j] <<"\n";
        }
    }
    cout << (dp[n][m] - 1 + Mod) % Mod <<"\n";

}


#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
4 5
1 3
4 1
1 2
3 2
2 1
return->break
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 6424 KB Output is correct
2 Correct 224 ms 6396 KB Output is correct
3 Correct 224 ms 6232 KB Output is correct
4 Correct 206 ms 6224 KB Output is correct
5 Correct 221 ms 6224 KB Output is correct
6 Correct 221 ms 6480 KB Output is correct
7 Correct 199 ms 6504 KB Output is correct
8 Correct 201 ms 6248 KB Output is correct
9 Correct 216 ms 6220 KB Output is correct
10 Correct 201 ms 6272 KB Output is correct
11 Correct 216 ms 6224 KB Output is correct
12 Correct 194 ms 6676 KB Output is correct
13 Correct 199 ms 6584 KB Output is correct
14 Correct 206 ms 6232 KB Output is correct
15 Correct 195 ms 6532 KB Output is correct
16 Correct 40 ms 5464 KB Output is correct
17 Correct 43 ms 5620 KB Output is correct
18 Correct 42 ms 5460 KB Output is correct
19 Correct 44 ms 5448 KB Output is correct
20 Correct 40 ms 6492 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 6424 KB Output is correct
2 Correct 224 ms 6396 KB Output is correct
3 Correct 224 ms 6232 KB Output is correct
4 Correct 206 ms 6224 KB Output is correct
5 Correct 221 ms 6224 KB Output is correct
6 Correct 221 ms 6480 KB Output is correct
7 Correct 199 ms 6504 KB Output is correct
8 Correct 201 ms 6248 KB Output is correct
9 Correct 216 ms 6220 KB Output is correct
10 Correct 201 ms 6272 KB Output is correct
11 Correct 216 ms 6224 KB Output is correct
12 Correct 194 ms 6676 KB Output is correct
13 Correct 199 ms 6584 KB Output is correct
14 Correct 206 ms 6232 KB Output is correct
15 Correct 195 ms 6532 KB Output is correct
16 Correct 40 ms 5464 KB Output is correct
17 Correct 43 ms 5620 KB Output is correct
18 Correct 42 ms 5460 KB Output is correct
19 Correct 44 ms 5448 KB Output is correct
20 Correct 40 ms 6492 KB Output is correct
21 Incorrect 362 ms 6996 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 6424 KB Output is correct
2 Correct 224 ms 6396 KB Output is correct
3 Correct 224 ms 6232 KB Output is correct
4 Correct 206 ms 6224 KB Output is correct
5 Correct 221 ms 6224 KB Output is correct
6 Correct 221 ms 6480 KB Output is correct
7 Correct 199 ms 6504 KB Output is correct
8 Correct 201 ms 6248 KB Output is correct
9 Correct 216 ms 6220 KB Output is correct
10 Correct 201 ms 6272 KB Output is correct
11 Correct 216 ms 6224 KB Output is correct
12 Correct 194 ms 6676 KB Output is correct
13 Correct 199 ms 6584 KB Output is correct
14 Correct 206 ms 6232 KB Output is correct
15 Correct 195 ms 6532 KB Output is correct
16 Correct 40 ms 5464 KB Output is correct
17 Correct 43 ms 5620 KB Output is correct
18 Correct 42 ms 5460 KB Output is correct
19 Correct 44 ms 5448 KB Output is correct
20 Correct 40 ms 6492 KB Output is correct
21 Incorrect 362 ms 6996 KB Output isn't correct
22 Halted 0 ms 0 KB -