Submission #962484

#	Time	Username	Problem	Language	Result	Execution time	Memory
962484		tvladm2009	Boat (APIO16_boat)	C++17	0 / 100	24 ms	17388 KiB

boat

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 500 + 7;
const int MAXV = 1000228;
const int Mod = 1e9 + 7;

int n;
int dp[MAXN][MAXN];
int f[MAXV], rf[MAXV];

int add(int a, int b) {
    return a + b >= Mod ? a + b - Mod : a + b;
}

int mul(int a, int b) {
    return 1LL * a * b % Mod;
}

int powm(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int dv(int a, int b) {
    return mul(a, powm(b, Mod - 2));
}

int comb(int n, int k) {
    return mul(f[n], mul(rf[k], rf[n - k]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);

    f[0] = 1;
    for (int i = 1; i < MAXV; i++) {
        f[i] = mul(f[i - 1], i);
    }
    rf[MAXV - 1] = dv(1, f[MAXV - 1]);
    for (int i = MAXV - 2; i >= 0; i--) {
        rf[i] = mul(rf[i + 1], i + 1);
    }

    cin >> n;
    vector<int> vals;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        vals.pb(l);
        vals.pb(r);
        res = add(res, r - l + 1);
    }
    sort(all(vals));
    vals.resize(unique(all(vals)) - vals.begin());
    vector<pair<int, int>> segments;
    for (int i = 0; i + 1 < sz(vals); i++) {
        segments.pb(mp(vals[i], vals[i + 1] - 1));
    }
    segments.back().second++;
    vector<int> lens;
    for (auto i: segments) {
        lens.pb(i.second - i.first + 1);
    }
    dp[0][0] = 1;
    for (int i = 1; i <= sz(lens); i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min(j, lens[i - 1]); k++) {
               dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - k], comb(lens[i - 1], k))); 
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        res = add(res, dp[sz(lens)][i]);
    }
    cout << res << '\n';
    return 0;
}

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