Submission #165383

#	Time	Username	Problem	Language	Result	Execution time	Memory
165383		combi1k1	Boat (APIO16_boat)	C++14	100 / 100	913 ms	2552 KiB

boat

#include<bits/stdc++.h>

using namespace std;

const int   N   = 505;
const int   mod = 1e9 + 7;

void add(int &a,int b)  {
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub(int &a,int b)  {
    a -= b;
    if (a <  0)
        a += mod;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}

int inv[N];

int a[N], b[N];
int f[N][1010];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    inv[1] = 1;

    for(int i = 2 ; i < N ; ++i)
        inv[i] = mul(inv[mod % i],mod - mod / i);

    int n;  cin >> n;

    vector<int> comp;

    for(int i = 1 ; i <= n ; ++i)   {
        cin >> a[i];    comp.push_back(a[i] - 1);
        cin >> b[i];    comp.push_back(b[i]);
    }
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());

    for(int i = 1 ; i <= n ; ++i)   {
        a[i] = lower_bound(comp.begin(),comp.end(),a[i]) - comp.begin();
        b[i] = lower_bound(comp.begin(),comp.end(),b[i]) - comp.begin();
    }
    for(int i = 0 ; i < comp.size() ; ++i)
        f[0][i] = 1;
    for(int i = 1 ; i <= n ; ++i)   {
        assert(a[i]);
        f[i][0] = 1;
        for(int j = a[i] ; j <= b[i] ; ++j) {
            f[i][j] = mul(f[i - 1][j - 1],comp[j] - comp[j - 1]);

            int cnt = 1;
            int Max = comp[j] - comp[j - 1];
            int way = Max - 1;

            for(int k = i - 1 ; k ; --k)    if (a[k] <= j && j <= b[k]) {
                way = mul(way,Max++);
                way = mul(way,inv[++cnt]);

                add(f[i][j],mul(f[k - 1][j - 1],way));
            }
        }
        for(int j = 1 ; j < comp.size() ; ++j)
            //cout << f[i][j] << " ",
            add(f[i][j],f[i - 1][j]),
            add(f[i][j],f[i][j - 1]),
            sub(f[i][j],f[i - 1][j - 1]);
        //cout << "\n";
    }

    int ans = f[n][comp.size() - 1];
    sub(ans,1);

    cout << ans << endl;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < comp.size() ; ++i)
                     ~~^~~~~~~~~~~~~
boat.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1 ; j < comp.size() ; ++j)
                         ~~^~~~~~~~~~~~~

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