Submission #80749

#	Time	Username	Problem	Language	Result	Execution time	Memory
80749		polyfish	Boat (APIO16_boat)	C++14	9 / 100	101 ms	11636 KiB

boat

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 502;
const int MOD = 1000000007;

int n;
int64_t f[MAX_N][MAX_N*2], ps[MAX_N][MAX_N*2], C[2*MAX_N][MAX_N], fact[MAX_N];
pair<int, int> s[MAX_N];
vector<pair<int, int> > t;

void enter() {
    cin >> n;
    for (int i=1; i<=n; ++i) {
        cin >> s[i].first >> s[i].second;
    }
}

int64_t pw(int64_t n, int k) {
    if (k==0)
        return 1;
    int64_t tmp = pw(n, k/2);
    if (k%2)
        return tmp * tmp % MOD * n % MOD;
    return tmp * tmp % MOD;
}

void init() {
    vector<int> b;
    for (int i=1; i<=n; ++i) {
        b.push_back(s[i].first);
        b.push_back(s[i].second+1);
    }
    sort(b.begin(), b.end());
    t.push_back(make_pair(0, 0));
    t.push_back(make_pair(0, 0));
    for (int i=0; i+1<b.size(); ++i) {
        if (b[i+1]-1>=b[i])
            t.push_back(make_pair(b[i], b[i+1]-1));
    }
    sort(t.begin(), t.end());
    fact[0] = 1;
    for (int i=1; i<=n; ++i)
        fact[i] = fact[i-1] * i % MOD;
    for (int i=1; i<t.size(); ++i) {
        int len = t[i].second - t[i].first + 1;
        int64_t tmp = 1;
        for (int k=1; k<=min(len, n); ++k) {
            tmp = tmp * (len-k+1) % MOD;
            C[i][k] = tmp * pw(fact[k], MOD-2) % MOD;
        }
    }
}

bool intersect(pair<int, int> p, pair<int, int> q) {
    return !(p.second < q.first || p.first>q.second);
}

void solve() {
    int64_t res = 0;
    f[0][1] = 1;
    for (int j=1; j<t.size(); ++j)
        ps[0][j] = 1;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<t.size(); ++j) {
            if (intersect(s[i], t[j])) {
                for (int k=i; k>=1; --k) {
                    if (!intersect(t[j], s[k]))
                        break;
                    f[i][j] = (f[i][j] + ps[k-1][j-1] * C[j][i-k+1]) % MOD;
                    //cerr << ps[k-1][j-1] << ' ' << C[t[j].first-t[j].second+1][i-k+1] << '\n';
                }
            }
            res = (res + f[i][j]) % MOD;
        }
        for (int j=1; j<t.size(); ++j)
            ps[i][j] = (ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + MOD + f[i][j]) % MOD;
    }
    cout << res;
}

int main() {
    //freopen("boat.inp", "r", stdin);
    //freopen("boat.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    enter();
    init();
    solve();
}

Compilation message (stderr)

boat.cpp: In function 'void init()':
boat.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i+1<b.size(); ++i) {
                   ~~~^~~~~~~~~
boat.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<t.size(); ++i) {
                   ~^~~~~~~~~
boat.cpp: In function 'void solve()':
boat.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=1; j<t.size(); ++j)
                   ~^~~~~~~~~
boat.cpp:65:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=1; j<t.size(); ++j) {
                       ~^~~~~~~~~
boat.cpp:76:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=1; j<t.size(); ++j)
                       ~^~~~~~~~~

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