oj.uz

Submission #80741

# Submission time Handle Problem Language Result Execution time Memory
80741 2018-10-22T07:36:56 Z polyfish Boat (APIO16_boat) C++14
0 / 100
 17 ms 8384 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8184 KB Output is correct
2 Incorrect 17 ms 8384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8184 KB Output is correct
2 Incorrect 17 ms 8384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 8384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8184 KB Output is correct
2 Incorrect 17 ms 8384 KB Output isn't correct
3 Halted 0 ms 0 KB -