Submission #80741

#	Time	Username	Problem	Language	Result	Execution time	Memory
80741		polyfish	Boat (APIO16_boat)	C++14	0 / 100	17 ms	8384 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[MAX_N][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;
    }
}

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) {
        t.push_back(make_pair(b[i], b[i+1]-1));
    }
    sort(t.begin(), t.end());
    for (int i=0; i<=n; ++i)
        C[i][i] = C[i][0] = 1;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<i; ++j)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % 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[t[j].first-t[j].second+1][i-k+1]) % MOD;
                }
            }
            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] + 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:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i+1<b.size(); ++i) {
                   ~~~^~~~~~~~~
boat.cpp: In function 'void solve()':
boat.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=1; j<t.size(); ++j)
                   ~^~~~~~~~~
boat.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=1; j<t.size(); ++j) {
                       ~^~~~~~~~~
boat.cpp:60:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=1; j<t.size(); ++j)
                       ~^~~~~~~~~

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