제출 #161114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161114		pzdba	Boat (APIO16_boat)	C++14	100 / 100	1726 ms	10448 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[501][1001];
int tmp[1001][501];
int D[1001][501], C[1001][1001];
int sum[1001][501];
vector<int> v;
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){
    int l = v[a]-v[a-1];
    if(b > l) return 0;
    else if(b == l) return 1;
    int mn = min(l-b, b);
    return tmp[a][mn]*1ll*inv[mn]%mod;
}

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);

    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=1;j<v.size();j++){
        for(int i=1;i<=n;i++){
            if(i == 1) tmp[j][i] = v[j]-v[j-1];
            else tmp[j][i] = tmp[j][i-1]*1ll*(v[j]-v[j-1]-i+1)%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++){
            for(int l=0;l<i;l++){
                sum[j][i] = (sum[j][i] + ncr(j, l+1)*1ll*C[i-1][l])%mod;
            }

            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);
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=1;j<v.size();j++){
                 ~^~~~~~~~~
boat.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<v.size();j++){
                     ~^~~~~~~~~
boat.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:42: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: 42 / 42