제출 #1131558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131558		garam1732	Boat (APIO16_boat)	C++20	0 / 100	13 ms	15168 KiB

boat

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 550;//100100*5;
const ll MOD = 1e9+7;
const ll INF = 2e18;

vector<ll> v;
pll arr[MAXN];
ll dp[MAXN][MAXN*2], sum[MAXN][MAXN*2]; // dp[i][j] : choose jth interval for ith school
ll comb[MAXN*2][MAXN], fac[MAXN], rfac[MAXN];
ll cnt[MAXN][MAXN*2];

ll pw(ll a, ll b) {
    if(b==0) return 1;
    ll x=pw(a*a%MOD, b>>1);
    if(b&1) x=x*a%MOD;
    return x;
}

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

    int n; cin>>n;
    for(int i=1; i<=n; i++) {
        cin >> arr[i].ff>>arr[i].ss;
        v.push_back(arr[i].ff); v.push_back(arr[i].ss+1);
    }

    v.push_back(-100);
    sort(all(v)); comp(v);

    fac[0] = 1;
    for(int i=1; i<=n; i++) fac[i]=fac[i-1]*i%MOD;
    rfac[n] = pw(fac[n], MOD-2);
    for(int i=n-1; i>=0; i--) rfac[i]=rfac[i+1]*(i+1)%MOD;

    int sz = v.size();
    for(int i=1; i<sz-1; i++) {
        ll l = v[i+1]-v[i], tmp=1;
        for(int j=0; j<=n; j++) {
            comb[i][j] = tmp*rfac[j]%MOD;
            tmp = tmp*(l+j+1)%MOD;
        }
    }

    for(int i=1; i<=n; i++) {
        arr[i].ff = lbd(v, arr[i].ff);
        arr[i].ss = lbd(v, arr[i].ss+1);//cout<<arr[i].ff<<bl<<arr[i].ss<<endl;

        for(int j=0; j<sz-1; j++) cnt[i][j] = cnt[i-1][j];
        for(int j=arr[i].ff; j<arr[i].ss; j++) cnt[i][j]++;
    }

    dp[0][0] = 1;
    for(int j=0; j<sz-1; j++) sum[0][j] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=arr[i].ff; j<arr[i].ss; j++) {
            for(int k=0; k<i; k++) {
                int t = cnt[i][j]-cnt[k][j];
                dp[i][j] += sum[k][j-1]*(comb[j][t]-comb[j][t-1])%MOD;
            }

            dp[i][j] = (dp[i][j]%MOD+MOD)%MOD;
        }

        sum[i][0] = dp[i][0];
        for(int j=1; j<sz-1; j++) sum[i][j] = (sum[i][j-1]+dp[i][j])%MOD;
    }

    // for(int i=1; i<=n; i++) {
    //     for(int j=0; j<sz-1; j++) cout<<dp[i][j]<<bl;
    //     cout<<endl;
    // }

    ll res=0;
    for(int i=1;i<=n;i++) res += sum[i][sz-2];
    cout<<res;
}

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