oj.uz

Submission #1085987

# Submission time Handle Problem Language Result Execution time Memory
1085987 2024-09-09T08:56:39 Z quanlt206 Boat (APIO16_boat) C++17
36 / 100
 2000 ms 34648 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }

/* END OF TEMPLATE */

const int N = 2e3 + 7;
const int mod = 1e9 + 7;

int n, m, a[N], b[N];

vector<int> E;

pii block[N];

int dp[2][2000][2000][2];

void add(int& x, int y) {
    if ((x+=y) >= mod) x-=mod;
}

int Ckn[N][N];

long long fact[N], inv_fact[N];

long long mul(long long a, long long b) {
    if (b == 0) return 1;
    ll tmp = mul(a, b / 2);
    tmp = tmp * tmp % mod;
    if (b & 1) tmp = tmp * a % mod;
    return tmp;
}

void buildCkn() {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv_fact[n] = mul(fact[n], mod - 2);
    for (int i = n - 1; i > 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
    for (int i = 1; i <= m; i++) {
        int sz = block[i].Y - block[i].X + 1;
        ll tich = 1;
        for (int j = sz; j > 0; j--) {
            tich = tich * j % mod;
            Ckn[i][sz - j + 1] = tich * inv_fact[sz - j + 1] % mod;
//            cout<<sz<<" "<<sz - j + 1<<" "<< Ckn[i][sz - j + 1]<<"\n";
            if (sz - j + 1 > n) break;
        }
    }
}

int dq(int i, int j, int k, int z) {
    if (i == 0) {
//        cout<<i<<" "<<j<<" "<<k<<" "<<z<<" | "<<Ckn[j][k]<<"\n";
        return Ckn[j][k];
    }
    if (j < 0) return 0;
    int& res = dp[i][j][k][z];
    if (res) return res;
    if (a[i] <= block[j].X && block[j].Y <= b[i]) add(res, dq(i - 1, j, k + 1, 0));
    if (z == 0) add(res, dq(i - 1, j, k, 0));
    if (j > 0 && k > 0) add(res, 1LL * dq(i, j - 1, 0, 1) * Ckn[j][k] % mod); else
    if (j > 0 && k == 0) add(res, dq(i, j - 1, 0, 1));
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    set<int> s;
    for (int i = 1; i <= n; i++) {
        cin>>a[i]>>b[i];
        s.insert(a[i]);
        s.insert(b[i]);
    }
    vector<int> E(s.begin(), s.end());
    for (int i = 0; i < E.size(); i++) {
        block[++m] = {E[i], E[i]};
        if (i + 1 < E.size() && E[i] + 1 <= E[i + 1] - 1) block[++m] = {E[i] + 1, E[i + 1] - 1};
    }
    buildCkn();
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= n; k++)
                for (int z = 0; z <= 1; z++) {
                    int& res = dp[i & 1][j][k][z];
                    res = 0;
                    if (i == 0) {
                        res = Ckn[j][k];
                        continue;
                    }
                    if (a[i] <= block[j].X && block[j].Y <= b[i]) add(res, dp[i & 1 ^ 1][j][k + 1][0]);
                    if (z == 0) add(res, dp[i & 1 ^ 1][j][k][0]);
                    if (j > 0 && k > 0) add(res, 1LL * dp[i & 1][j - 1][0][1] * Ckn[j][k] % mod); else
                    if (j > 0 && k == 0) add(res, dp[i & 1][j - 1][0][1]);
                }
    cout<<dp[n & 1][m][0][0];
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < E.size(); i++) {
      |                     ~~^~~~~~~~~~
boat.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         if (i + 1 < E.size() && E[i] + 1 <= E[i + 1] - 1) block[++m] = {E[i] + 1, E[i + 1] - 1};
      |             ~~~~~~^~~~~~~~~~
boat.cpp:128:81: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  128 |                     if (a[i] <= block[j].X && block[j].Y <= b[i]) add(res, dp[i & 1 ^ 1][j][k + 1][0]);
      |                                                                               ~~^~~
boat.cpp:129:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  129 |                     if (z == 0) add(res, dp[i & 1 ^ 1][j][k][0]);
      |                                             ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 22616 KB Output is correct
2 Correct 1709 ms 22732 KB Output is correct
3 Correct 1790 ms 22084 KB Output is correct
4 Correct 1794 ms 22084 KB Output is correct
5 Correct 1801 ms 21896 KB Output is correct
6 Correct 1752 ms 22080 KB Output is correct
7 Correct 1667 ms 22820 KB Output is correct
8 Correct 1678 ms 22616 KB Output is correct
9 Correct 1752 ms 22820 KB Output is correct
10 Correct 1761 ms 22616 KB Output is correct
11 Correct 1792 ms 22616 KB Output is correct
12 Correct 1779 ms 22816 KB Output is correct
13 Correct 1753 ms 23384 KB Output is correct
14 Correct 1812 ms 22616 KB Output is correct
15 Correct 1767 ms 22820 KB Output is correct
16 Correct 318 ms 7000 KB Output is correct
17 Correct 332 ms 5660 KB Output is correct
18 Correct 302 ms 5468 KB Output is correct
19 Correct 316 ms 5468 KB Output is correct
20 Correct 307 ms 5464 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 22616 KB Output is correct
2 Correct 1709 ms 22732 KB Output is correct
3 Correct 1790 ms 22084 KB Output is correct
4 Correct 1794 ms 22084 KB Output is correct
5 Correct 1801 ms 21896 KB Output is correct
6 Correct 1752 ms 22080 KB Output is correct
7 Correct 1667 ms 22820 KB Output is correct
8 Correct 1678 ms 22616 KB Output is correct
9 Correct 1752 ms 22820 KB Output is correct
10 Correct 1761 ms 22616 KB Output is correct
11 Correct 1792 ms 22616 KB Output is correct
12 Correct 1779 ms 22816 KB Output is correct
13 Correct 1753 ms 23384 KB Output is correct
14 Correct 1812 ms 22616 KB Output is correct
15 Correct 1767 ms 22820 KB Output is correct
16 Correct 318 ms 7000 KB Output is correct
17 Correct 332 ms 5660 KB Output is correct
18 Correct 302 ms 5468 KB Output is correct
19 Correct 316 ms 5468 KB Output is correct
20 Correct 307 ms 5464 KB Output is correct
21 Execution timed out 2049 ms 34648 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8284 KB Output is correct
2 Correct 30 ms 8280 KB Output is correct
3 Correct 37 ms 8284 KB Output is correct
4 Correct 30 ms 8284 KB Output is correct
5 Correct 31 ms 8284 KB Output is correct
6 Correct 31 ms 8284 KB Output is correct
7 Correct 31 ms 8284 KB Output is correct
8 Correct 32 ms 8280 KB Output is correct
9 Correct 31 ms 8280 KB Output is correct
10 Correct 31 ms 8284 KB Output is correct
11 Correct 38 ms 8284 KB Output is correct
12 Correct 30 ms 8284 KB Output is correct
13 Correct 32 ms 8492 KB Output is correct
14 Correct 33 ms 8280 KB Output is correct
15 Correct 33 ms 8540 KB Output is correct
16 Correct 15 ms 5976 KB Output is correct
17 Correct 14 ms 5980 KB Output is correct
18 Correct 14 ms 6084 KB Output is correct
19 Correct 14 ms 6084 KB Output is correct
20 Correct 15 ms 4188 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 22616 KB Output is correct
2 Correct 1709 ms 22732 KB Output is correct
3 Correct 1790 ms 22084 KB Output is correct
4 Correct 1794 ms 22084 KB Output is correct
5 Correct 1801 ms 21896 KB Output is correct
6 Correct 1752 ms 22080 KB Output is correct
7 Correct 1667 ms 22820 KB Output is correct
8 Correct 1678 ms 22616 KB Output is correct
9 Correct 1752 ms 22820 KB Output is correct
10 Correct 1761 ms 22616 KB Output is correct
11 Correct 1792 ms 22616 KB Output is correct
12 Correct 1779 ms 22816 KB Output is correct
13 Correct 1753 ms 23384 KB Output is correct
14 Correct 1812 ms 22616 KB Output is correct
15 Correct 1767 ms 22820 KB Output is correct
16 Correct 318 ms 7000 KB Output is correct
17 Correct 332 ms 5660 KB Output is correct
18 Correct 302 ms 5468 KB Output is correct
19 Correct 316 ms 5468 KB Output is correct
20 Correct 307 ms 5464 KB Output is correct
21 Execution timed out 2049 ms 34648 KB Time limit exceeded
22 Halted 0 ms 0 KB -