제출 #110905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110905		TAISA_	Boat (APIO16_boat)	C++14	0 / 100	15 ms	8448 KiB

boat

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
ll mpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1){
            res=res*x%MOD;
        }
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<ll> a(n+1),b(n+1),v,inv(n+10);
    v.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }
    for(int i=1;i<=n;i++){
        inv[i]=mpow(i,MOD-2LL);
    }
    v.push_back(0);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(all(v),a[i])-v.begin();
        b[i]=lower_bound(all(v),b[i]+1)-v.begin()-1;
    }
    int m=v.size();
    auto dp=make_v<ll>(n+10,m+10);
    auto sum=make_v<ll>(n+10,m+10);
    dp[0][0]=1;
    for(int j=0;j<=m;j++){
        sum[0][j]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=b[i];j++){
            ll c=v[j+1]-v[j],x=v[j+1]-v[j],y=1;
            for(int k=i-1;k>=0;k--){
                dp[i][j]+=c*sum[k][j-1]%MOD;
                dp[i][j]%=MOD;
                if(a[k]<=j&&j<=b[k]){
                    c*=(x+1LL)*inv[y+1]%MOD;
                    c%=MOD;
                    x++;
                    y++;
                }
            }
            ans%=MOD;
        }
        sum[i][0]=dp[i][0];
            for(int j=1;j<=m;j++){
                sum[i][j]=sum[i][j-1]+dp[i][j];
                sum[i][j]%=MOD;
            }
            ans+=sum[i][m];
    }
    cout<<ans<<endl;
}

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