제출 #1294467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294467		notisora	Boat (APIO16_boat)	C++20	100 / 100	230 ms	584 KiB

boat

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int N = 3005;
ll dp[N], g[N], c[N];
struct T{int l,r;};

ll pw(ll a, ll b){
    ll r=1;
    while(b){
        if(b&1) r=r*a%modulo;
        a=a*a%modulo;
        b>>=1;
    }
    return r;
}
ll iv(ll n){return pw(n, modulo-2);}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("i.INP","r",stdin);

    int n;
    if(!(cin >> n)) return 0;
    vector<T> a(n);
    vector<int> x;
    for(int i=0; i<n; ++i){
        cin >> a[i].l >> a[i].r;
        x.pb(a[i].l);
        x.pb(a[i].r + 1);
    }
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());

    for(int i=0; i < x.size()-1; ++i){
        int L = x[i];
        int R = x[i+1] - 1;
        int len = R - L + 1;
        if(len <= 0) continue;

        vector<int> v;
        for(int j=0; j<n; ++j)
            if(a[j].l <= L && a[j].r >= R) v.pb(j);

        if(v.empty()) continue;
        int m = v.size();
        c[0] = 1;
        for(int k=1; k <= m+1; ++k)
            c[k] = c[k-1] * (len - k + 1) % modulo * iv(k) % modulo;

        for(int k=0; k<=m+1; ++k) g[k] = 0;

        vector<pair<int, ll>> up;
        ll s = 0;
        int p = 0;

        for(int j=0; j<n; ++j){
            ll h = (s + 1) % modulo;
            if(p < m && v[p] == j){
                ll val = h * c[1] % modulo;
                for(int k=1; k <= p+1; ++k)
                    val = (val + g[k] * c[k+1]) % modulo;
                up.pb({j, val});

                for(int k=p+1; k>=1; --k) g[k+1] = (g[k+1] + g[k]) % modulo;
                g[1] = (g[1] + h) % modulo;
                p++;
            }
            s = (s + dp[j]) % modulo;
        }
        for(auto& it : up) dp[it.fi] = (dp[it.fi] + it.se) % modulo;
    }

    ll ans = 0;
    for(int i=0; i<n; ++i) ans = (ans + dp[i]) % modulo;
    cout << ans;
}

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