Submission #737229

#	Time	Username	Problem	Language	Result	Execution time	Memory
737229		colossal_pepe	Boat (APIO16_boat)	C++17	0 / 100	20 ms	9292 KiB

boat

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;
const int N = 100;

int n, l[N + 5], r[N + 5], C[2 * N + 5][N + 5], dp[N + 5][2 * N + 5][N + 5];
vector<int> v;

ll modPow(ll a, ll b) {
    if (b == 0) return 1;
    ll ret = modPow(a, b / 2);
    ret *= ret;
    ret %= MOD;
    if (b % 2) {
        ret *= a;
        ret %= MOD;
    }
    return ret;
}

ll modDivide(ll a, ll b) {
    return (a * modPow(b, MOD - 2)) % MOD;
}

void beautify() {
    { // filling v
        set<int> s;
        for (int i = 0; i < n; i++) {
            if (s.find(l[i]) == s.end()) {
                s.insert(l[i]);
                v.push_back(l[i]);
            }
            if (s.find(r[i]) == s.end()) {
                s.insert(r[i]);
                v.push_back(r[i]);
            }
        }
        sort(v.begin(), v.end());
    }
    for (int i = 0; i + 1 < v.size(); i++) {
        int len = v[i + 1] - v[i] + (i + 2 == v.size());
        ll a, b;
        C[i][0] = a = b = 1;
        for (int j = 1; j <= min(N, len); j++) {
            a *= len - j + 1;
            a %= MOD;
            b *= j;
            b %= MOD;
            C[i][j] = modDivide(a, b);
            // cout << len << ' ' << j << ' ' << C[i][j] << endl;
        }
    }
}

int brutus(int i, int j, int k) {
    if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
    if (i >= n) return C[j][k];
    if (dp[i][j][k] != -1) return dp[i][j][k];
    ll ret = 0;
    ret = brutus(i + 1, j, k);
    ret += (brutus(i, j + 1, 0) * C[j][k]) % MOD;
    ret %= MOD;
    if (i < n and l[i] <= v[j] and v[j + 1] <= r[i]) {
        ret += brutus(i + 1, j, k + 1);
        ret %= MOD;
    }
    dp[i][j][k] = ret;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // cout << modDivide(169, 1) << endl;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }
    beautify();
    memset(dp, -1, sizeof dp);
    int ans = brutus(0, 0, 0);
    ans -= 1;
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void beautify()':
boat.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i + 1 < v.size(); i++) {
      |                     ~~~~~~^~~~~~~~~~
boat.cpp:48:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         int len = v[i + 1] - v[i] + (i + 2 == v.size());
      |                                      ~~~~~~^~~~~~~~~~~
boat.cpp: In function 'int brutus(int, int, int)':
boat.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
      |         ~~~~~~^~~~~~~~~~~
boat.cpp:63:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (j + 1 >= v.size() or k > v[j + 1] - v[j] + (j + 2 == v.size())) return 0;
      |                                                     ~~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42