Submission #152795

#	Time	Username	Problem	Language	Result	Execution time	Memory
152795		mhy908	Boat (APIO16_boat)	C++14	100 / 100	620 ms	4508 KiB

boat

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define llinf 8987654321987654321
#define mod 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
vector<LL> id;
int n;
LL a[1010], b[1010];
LL dp[1010][1010], inv[1010], len[1010];
LL power(LL a, LL b)
{
    if(!b)return 1;
    LL ret=power(a, b/2);
    return b%2?ret*ret%mod*a%mod:ret*ret%mod;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=1000; i++)inv[i]=power(i, mod-2);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
        id.pb(a[i]-1);
        id.pb(b[i]);
    }
    sort(all(id));
    id.erase(unique(all(id)), id.end());
    for(int i=1; i<=n; i++){
        LL temp=lower_bound(all(id), a[i]-1)+1-id.begin();
        a[i]=temp;
        temp=lower_bound(all(id), b[i])+1-id.begin();
        b[i]=temp;
    }
    int siz=id.size();
    len[1]=id[0];
    for(int i=1; i<=siz; i++)len[i]=id[i-1]-id[i-2];
    for(int i=1;i<=n;i++){
        for(int j=1; j<=siz; j++){
            if(i==1&&a[i]<j&&j<=b[i])dp[i][j]=(dp[i][j]+len[j])%mod;
            else{
                if(a[i]<j&&j<=b[i]){
                    dp[i][j]=(dp[i][j]+len[j]*(1+dp[i-1][j-1]))%mod;
                    int cnt=1;
                    LL sum=len[j]-1;
                    for(int k=i-1; k>=1; k--){
                        if(a[k]<j&&j<=b[k]){
                            cnt++;
                            sum=sum*(len[j]+cnt-2)%mod*inv[cnt]%mod;
                            dp[i][j]=(dp[i][j]+sum+sum*dp[k-1][j-1])%mod;
                        }
                    }
                }
            }
            dp[i][j]=(dp[i][j]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mod)%mod;
        }
    }
    printf("%lld", dp[n][siz]);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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