Submission #218037

#	Time	Username	Problem	Language	Result	Execution time	Memory
218037		perveevm	Boat (APIO16_boat)	C++14	9 / 100	551 ms	2432 KiB

boat

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238;
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 510;
const int MOD = (int)1e9 + 7;

int add(int a, int b, int mod = MOD) {
    if (a + b >= mod) {
        return a + b - mod;
    }
    return a + b;
}

int sub(int a, int b, int mod = MOD) {
    if (a - b < 0) {
        return a - b + mod;
    }
    return a - b;
}

int mul(int a, int b, int mod = MOD) {
    return (int)(1ll * a * b % mod);
}

int binpow(int a, int n, int mod = MOD) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        return binpow(mul(a, a, mod), n / 2, mod);
    } else {
        return mul(binpow(a, n - 1, mod), a, mod);
    }
}

int rev(int a, int mod = MOD) {
    return binpow(a, mod - 2, mod);
}

int a[N], b[N];
int dp[2 * N][N];
int f[2 * N], rf[2 * N];

void precalc() {
    f[0] = 1;
    rf[0] = 1;

    for (int i = 1; i < 2 * N; ++i) {
        f[i] = mul(f[i - 1], i);
        rf[i] = rev(f[i]);
    }
}

int C(int n, int k) {
    if (n < k) {
        return 0;
    }
    return mul(f[n], mul(rf[k], rf[n - k]));
}

void run() {
    precalc();

    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i], &b[i]);
        ++b[i];
    }

    std::vector<int> trans;
    for (int i = 1; i <= n; ++i) {
        trans.push_back(a[i]);
        trans.push_back(b[i]);
    }

    std::sort(trans.begin(), trans.end());
    trans.resize(std::unique(trans.begin(), trans.end()) - trans.begin());

    for (int i = 1; i <= n; ++i) {
        a[i] = std::lower_bound(trans.begin(), trans.end(), a[i]) - trans.begin() + 1;
        b[i] = std::lower_bound(trans.begin(), trans.end(), b[i]) - trans.begin() + 1;
    }

    dp[0][0] = 1;
    // dp[i][j] - ans if last segment is i'th or less and last boat is j'th

    for (int i = 1; i < (int)trans.size(); ++i) {
        dp[i][0] = 1;

        for (int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];

            if (i < a[j] || b[j] <= i) {
                continue;
            }

            int len = trans[i] - trans[i - 1];
            int cnt = 1;

            for (int k = j - 1; k >= 0; --k) {
                dp[i][j] = add(dp[i][j], mul(dp[i - 1][k], C(len + cnt - 1, cnt)));

                if (a[k] <= i && i < b[k]) {
                    ++cnt;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = add(ans, dp[(int)trans.size() - 1][i]);
    }

    printf("%d\n", ans);
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    auto start = std::chrono::high_resolution_clock::now();
    run();
    auto end = std::chrono::high_resolution_clock::now();

    #ifdef PERVEEVM_LOCAL
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:149:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
     auto start = std::chrono::high_resolution_clock::now();
          ^~~~~
boat.cpp:151:10: warning: variable 'end' set but not used [-Wunused-but-set-variable]
     auto end = std::chrono::high_resolution_clock::now();
          ^~~
boat.cpp: In function 'void run()':
boat.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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