Submission #161087

#	Time	Username	Problem	Language	Result	Execution time	Memory
161087		pzdba	Boat (APIO16_boat)	C++14	58 / 100	2029 ms	10400 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int binPow(int a, int b){
    int ans = 1;
    while(b){
        if(b%2 == 1) ans = ans*1ll*a%mod;
        a = a*1ll*a%mod;
        b/=2;
    }
    return ans;
}
int f[1001], inv[1001], a[501], b[501], l[501], r[501];
int ncr(int a, int b){
    if(b > a) return 0;
    int mn = min(a-b, b), mx = max(a-b, b);
    int ans = 1;
    for(int i=a;i>mx;i--) ans = (ans*1ll*i)%mod;
    return ans*1ll*inv[mn]%mod;
}

int dp[501][1001];
int D[1001][501], C[1001][1001];
int sum[1001][501];
int main(){
    C[0][0] = 1;
    for(int i=1;i<=1000;i++){
        C[i][0] = C[i][i] = 1;
        for(int j=1;j<i;j++){
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
        }
    }
    f[0] = 1;
    for(int i=1;i<=1000;i++) f[i] = f[i-1]*1ll*i%mod;
    for(int i=0;i<=1000;i++) inv[i] = binPow(f[i], mod-2);
    int n;
    scanf("%d", &n);

    vector<int> v;
    for(int i=1;i<=n;i++){
        scanf("%d%d", &a[i], &b[i]);
        v.push_back(a[i]-1);
        v.push_back(b[i]);
    }   
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=1;i<=n;i++){
        l[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        r[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
    }
    for(int i=1;i<v.size();i++){
        for(int j=1;j<=n;j++){
            D[i][j] = ncr(v[i]-v[i-1], j);
            for(int l=0;l<j;l++){
                sum[i][j] = (sum[i][j] + D[i][l+1]*1ll*C[j-1][l])%mod;
            }
        }
    }
    for(int j=0;j<=1000;j++) dp[0][j] = 1;
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<v.size();j++){
            if(l[i] <= j && j <= r[i]){
                int cnt = 0;
                for(int k=i;k>=1;k--){
                    if(l[k] <= j && j <= r[k]) cnt++;
                    dp[i][j] = (dp[i][j] + dp[k-1][j-1]*1ll*sum[j][cnt])%mod;
                }
            }
            dp[i][j] = (dp[i][j] + dp[i][j-1])%mod;
        }
        ans = (ans + dp[i][v.size()-1])%mod;
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<v.size();i++){
                 ~^~~~~~~~~
boat.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<v.size();j++){
                     ~^~~~~~~~~
boat.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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