Submission #47972

#	Time	Username	Problem	Language	Result	Execution time	Memory
47972		3zp	Boat (APIO16_boat)	C++14	9 / 100	43 ms	9440 KiB

boat

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5009], b[5009];
ll mod = 1e9+7;
ll c[2009];
ll l[5009], r[5009];
ll dp[5009][4009];
ll in[5009];
vector<pair<ll,ll> > d;
main(){
    ll n;
    cin >> n;
    for(ll i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        c[2*i] = a[i];
        c[2*i + 1] = b[i];
    }
    sort(c, c+2*n);
    in[0] = 1;
    in[1] = 1;
    for (int i = 2; i <= n; i++)
        in[i] = in[mod % i] *(mod - mod / i) % mod;
    for(ll i = 0; i < 2*n; i++){
        if(i < 2*n-1 && c[i] == c[i+1]) continue;
        d.push_back({c[i], c[i]});
        if(i == 2*n-1 || c[i+1] == c[i]+1) continue;
        d.push_back({c[i]+1, c[i+1]-1});
    }
    for (ll i= 0; i < n; i++){
        for (ll j = 0; j < d.size(); j++){
            if(a[i] == d[j].first) {l[i] = j; break;}
        }
        for (ll j = 0; j < d.size(); j++){
            if(b[i] == d[j].second) r[i] = j;
        }
    }
    ll N = d.size();
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < N; j++){
            if(j) dp[i][j] = (dp[i][j-1]);
            ll L = d[j].second - d[j].first + 1;
            ll W = 1;
            for (ll t = i; t >= 0; t--){
                if(l[t] > j || r[t] < j) break;
                W = W*(L - (i -t)) % mod *in[i-t+1] % mod;
                if(t == 0) dp[i][j] = (dp[i][j] + W) % mod; else
                if(j == 0) dp[i][j] = (dp[i][j] + W) % mod; else
                dp[i][j] = (dp[i][j] + W*dp[t-1][j-1]) % mod;

            }
        }

        for(ll j = 0; j < N; j++){

            if(i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
            else dp[i][j] = (dp[i][j] + 1) % mod;
        }
    }
    cout << (dp[n-1][N-1] -1 + mod)% mod << endl;
    return 0;
}

Compilation message (stderr)

boat.cpp:11:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
boat.cpp: In function 'int main()':
boat.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j < d.size(); j++){
                        ~~^~~~~~~~~~
boat.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j < d.size(); j++){
                        ~~^~~~~~~~~~

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