oj.uz

Submission #839858

# Submission time Handle Problem Language Result Execution time Memory
839858 2023-08-30T19:03:27 Z popovicirobert Boat (APIO16_boat) C++14
36 / 100
 284 ms 13272 KB 
#include <bits/stdc++.h>
 
using namespace std;

constexpr int MOD = (int) 1e9 + 7;

inline int logpow(int a, int b) {
    int answer = 1;
    while (b > 0) {
        if (b & 1) answer = (1LL * answer * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return answer;
}

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

constexpr int MAXN = 505;

int dp[2][3 * MAXN + 1][MAXN + 1];
int sp[2][3 * MAXN + 1];
 
int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    
    vector<int> a(n + 1), b(n + 1);
    vector<int> x;

    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        x.push_back(a[i]);
        x.push_back(b[i]);
    }

    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());

    vector<pair<int, int>> segs;
    segs.push_back({0, 0});

    for (int i = 0; i < (int)x.size(); i++) {
        segs.push_back({x[i], x[i]});
        if (i + 1 < (int)x.size() && x[i] + 1 <= x[i + 1] - 1) {    
            segs.push_back({x[i] + 1, x[i + 1] - 1});
        }
    }

    vector<vector<int>> comb(segs.size(), vector<int>(n + 1));
    for (int i = 0; i < (int)segs.size(); i++) {
        auto s = segs[i];
        int size = s.second - s.first + 1;

        int fact = 1, prod = 1;

        comb[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            if (j > size) {
                comb[i][j] = 0;
                continue;
            }
            prod = (1LL * prod * (size - j + 1)) % MOD;
            fact = (1LL * fact * j) % MOD;
            comb[i][j] = (1LL * logpow(fact, MOD - 2) * prod) % MOD;
        }
    }

    // for (auto itr : segs) {
    //     cerr << itr.first << " " << itr.second << "    "; 
    // }
    // cerr << "\n";

    auto Comb = [&segs, &comb](int j, int k) {
        return segs[j].second - segs[j].first + 1 < k ? 0 : comb[j][k];
    };

    auto Calc = [&segs, &Comb](int i) {
        for (int j = 0; j < (int)segs.size(); j++) {
            for (int k = 1; k <= i + 1; k++) {
                int curr = dp[i & 1][j][k];
                if (curr == 0) continue;

                sp[i & 1][j] = (sp[i & 1][j] + 1LL * Comb(j, k) * curr) % MOD;
            }
        }

        for (int j = 1; j < (int)segs.size(); j++) {
            add(sp[i & 1][j], sp[i & 1][j - 1]);
        }
    };

    dp[0][0][1] = 1;
    Calc(0);

    for (int i = 1; i <= n; i++) {
        memset(sp[i & 1], 0, sizeof(sp[i & 1]));
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));

        for (int j = 0; j < (int)segs.size(); j++) {
            for (int k = 1; k <= i; k++) {
                dp[i & 1][j][k] = dp[1 - i & 1][j][k];
            }
            if (a[i] <= segs[j].first && segs[j].second <= b[i]) {
                add(dp[i & 1][j][1], sp[1 - i & 1][j - 1]);
                for (int k = 1; k <= i; k++) {    
                    add(dp[i & 1][j][k], dp[1 - i & 1][j][k - 1]);
                }
            }
        }

        // for (int j = 0; j < (int)segs.size(); j++) {
        //     cerr << sp[1 - i & 1][j] << " "; 
        // }
        // cerr << "\n";

        // for (int j = 0; j < (int)segs.size(); j++) {
        //     for (int k = 1; k <= i; k++) {
        //         cerr << dp[i & 1][j][k] << " ";
        //     }
        //     cerr << "\n";
        // }
        // cerr << "\n";

        Calc(i);
    }

    cout << (sp[n & 1][(int)segs.size() - 1] + MOD - 1) % MOD;
 
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:113:40: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  113 |                 dp[i & 1][j][k] = dp[1 - i & 1][j][k];
      |                                      ~~^~~
boat.cpp:116:43: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  116 |                 add(dp[i & 1][j][1], sp[1 - i & 1][j - 1]);
      |                                         ~~^~~
boat.cpp:118:47: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  118 |                     add(dp[i & 1][j][k], dp[1 - i & 1][j][k - 1]);
      |                                             ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 8288 KB Output is correct
2 Correct 274 ms 8336 KB Output is correct
3 Correct 241 ms 8328 KB Output is correct
4 Correct 244 ms 8332 KB Output is correct
5 Correct 247 ms 8268 KB Output is correct
6 Correct 236 ms 8224 KB Output is correct
7 Correct 264 ms 8328 KB Output is correct
8 Correct 242 ms 8332 KB Output is correct
9 Correct 237 ms 8268 KB Output is correct
10 Correct 254 ms 8328 KB Output is correct
11 Correct 246 ms 8272 KB Output is correct
12 Correct 250 ms 8336 KB Output is correct
13 Correct 248 ms 8268 KB Output is correct
14 Correct 239 ms 8332 KB Output is correct
15 Correct 242 ms 8328 KB Output is correct
16 Correct 69 ms 6680 KB Output is correct
17 Correct 71 ms 6720 KB Output is correct
18 Correct 67 ms 6612 KB Output is correct
19 Correct 72 ms 6708 KB Output is correct
20 Correct 67 ms 6716 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 8288 KB Output is correct
2 Correct 274 ms 8336 KB Output is correct
3 Correct 241 ms 8328 KB Output is correct
4 Correct 244 ms 8332 KB Output is correct
5 Correct 247 ms 8268 KB Output is correct
6 Correct 236 ms 8224 KB Output is correct
7 Correct 264 ms 8328 KB Output is correct
8 Correct 242 ms 8332 KB Output is correct
9 Correct 237 ms 8268 KB Output is correct
10 Correct 254 ms 8328 KB Output is correct
11 Correct 246 ms 8272 KB Output is correct
12 Correct 250 ms 8336 KB Output is correct
13 Correct 248 ms 8268 KB Output is correct
14 Correct 239 ms 8332 KB Output is correct
15 Correct 242 ms 8328 KB Output is correct
16 Correct 69 ms 6680 KB Output is correct
17 Correct 71 ms 6720 KB Output is correct
18 Correct 67 ms 6612 KB Output is correct
19 Correct 72 ms 6708 KB Output is correct
20 Correct 67 ms 6716 KB Output is correct
21 Runtime error 14 ms 13272 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6484 KB Output is correct
2 Correct 18 ms 6408 KB Output is correct
3 Correct 19 ms 6472 KB Output is correct
4 Correct 19 ms 6516 KB Output is correct
5 Correct 24 ms 6604 KB Output is correct
6 Correct 23 ms 6484 KB Output is correct
7 Correct 23 ms 6484 KB Output is correct
8 Correct 27 ms 6484 KB Output is correct
9 Correct 23 ms 6436 KB Output is correct
10 Correct 23 ms 6428 KB Output is correct
11 Correct 22 ms 6484 KB Output is correct
12 Correct 22 ms 6512 KB Output is correct
13 Correct 20 ms 6472 KB Output is correct
14 Correct 19 ms 6484 KB Output is correct
15 Correct 21 ms 6512 KB Output is correct
16 Correct 13 ms 6316 KB Output is correct
17 Correct 12 ms 6356 KB Output is correct
18 Correct 16 ms 6540 KB Output is correct
19 Correct 12 ms 6340 KB Output is correct
20 Correct 14 ms 6420 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 8288 KB Output is correct
2 Correct 274 ms 8336 KB Output is correct
3 Correct 241 ms 8328 KB Output is correct
4 Correct 244 ms 8332 KB Output is correct
5 Correct 247 ms 8268 KB Output is correct
6 Correct 236 ms 8224 KB Output is correct
7 Correct 264 ms 8328 KB Output is correct
8 Correct 242 ms 8332 KB Output is correct
9 Correct 237 ms 8268 KB Output is correct
10 Correct 254 ms 8328 KB Output is correct
11 Correct 246 ms 8272 KB Output is correct
12 Correct 250 ms 8336 KB Output is correct
13 Correct 248 ms 8268 KB Output is correct
14 Correct 239 ms 8332 KB Output is correct
15 Correct 242 ms 8328 KB Output is correct
16 Correct 69 ms 6680 KB Output is correct
17 Correct 71 ms 6720 KB Output is correct
18 Correct 67 ms 6612 KB Output is correct
19 Correct 72 ms 6708 KB Output is correct
20 Correct 67 ms 6716 KB Output is correct
21 Runtime error 14 ms 13272 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -