Submission #199231

#	Time	Username	Problem	Language	Result	Execution time	Memory
199231		anachor	Boat (APIO16_boat)	C++14	100 / 100	374 ms	16248 KiB

boat

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

const int N = 1005, M = 1e9+7;
int l[N], r[N];
int st[N], len[N];

typedef long long LL;
LL dp[N][N];
LL sum[N][N];

LL power(LL a, LL p) {
    if (p==0)   return 1;
    LL ans = power(a, p/2);
    ans = (ans * ans)%M;
    if (p%2)    ans = (ans * a)%M;
    return ans;
}

LL f[N][N];
LL inv[N];

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

    int n;
    cin>>n;
    map<int, int> mp;

    for (int i=1; i<=n; i++) {
        cin>>l[i]>>r[i];
        mp[l[i]] = mp[r[i]+1] = 0;
    }

    int sz = 0;
    for (auto &pr: mp) {
        pr.second = ++sz;
        st[sz] = pr.first;
    }

    for (int i=1; i<=n; i++)    inv[i] = power(i, M-2);
    for (int i=1; i<sz; i++)    {
        len[i] = st[i+1] - st[i];
        f[i][0] = 1;
        for (int j=1; j<=n; j++) {
            f[i][j] = (f[i][j-1]*(len[i]+j-1))%M;
            f[i][j] = (f[i][j]*inv[j])%M;
        }
    }

    dp[0][0] = 1;
    for (int i=0; i<=sz; i++)   sum[0][i] = 1;

    long long ans = 0;

    for (int i=1; i<=n; i++) {
        int ll = mp[l[i]], rr = mp[r[i]+1];

        for (int k=1; k<=sz; k++)  {
            if (!(l[i] <= st[k] && st[k] <= r[i]))  continue;
            int pos = 0;
            for (int j=i; j>=1; j--) {
                if (l[j] <= st[k] && st[k] <= r[j]) pos++;
                dp[i][k] = (dp[i][k] + f[k][pos] * sum[j-1][k-1])%M;
            }
        }

        for (int k=1; k<=sz; k++)
            sum[i][k] = (sum[i][k-1] + dp[i][k])%M;
        ans = (ans + sum[i][sz])%M;
    }

    cout<<ans<<endl;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:58:13: warning: unused variable 'll' [-Wunused-variable]
         int ll = mp[l[i]], rr = mp[r[i]+1];
             ^~
boat.cpp:58:28: warning: unused variable 'rr' [-Wunused-variable]
         int ll = mp[l[i]], rr = mp[r[i]+1];
                            ^~

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