Submission #958114

#	Time	Username	Problem	Language	Result	Execution time	Memory
958114		thomas_li	Boat (APIO16_boat)	C++17	100 / 100	1253 ms	37492 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A,class B> void cmx(A& x, B y) {x=max<A>(x,y);}
template<class A,class B> void cmn(A& x, B y) {x=min<A>(x,y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MM = 1e3+20,MOD = 1e9+7;

typedef int T;
int n; T dp[MM][MM]; vi pts; vector<pii> grps;
pii school[MM]; int lft[MM],rit[MM];
T big_c[MM][MM];

T pre[MM][2][MM],C[MM][MM];
int fpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1) res = 1ll*res*x%MOD;
		x = 1ll*x*x%MOD;
		y /= 2;
	}
	return res;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    C[0][0] = 1;
    rep(i,1,MM){
        rep(j,0,i+1){
            C[i][j] = C[i-1][j];
            if(j) C[i][j] = (C[i][j]+C[i-1][j-1])%MOD;
        }
    }
    cin >> n;
    rep(i,1,n+1){
        int a,b; cin >> a >> b;
        school[i] = {a,b};
        pts.PB(a-1);
        pts.PB(b);
    }
    pts.PB(-1);
    sort(all(pts));     
    rep(i,0,sz(pts)-1){
        if(pts[i] < pts[i+1]) grps.PB({pts[i]+1,pts[i+1]});
    }
    int m = sz(grps);
    rep(i,1,n+1){
        auto[a,b] = school[i];
        lft[i] = -1;
        rep(j,0,m){
            auto[l,r] = grps[j];
            if(a <= l && r <= b){
                rit[i] = j;
                if(!~lft[i]) lft[i] = j;
            }
        }
        assert(~lft[i]);
    } 
    rep(j,0,m){
        dp[0][j] = 1;
    }
    
    auto fC = [&](int x, int y){
        if(x < 0 || x < y || y < 0) return T(0);
        return C[x][y];
    };
    rep(i,1,m){
        int len = grps[i].SD-grps[i].FS+1;
        T kf = 1,num = 1;
        rep(j,1,min(len+1,n+1)){
            num = num*(len-j+1)%MOD;
            kf = kf*j%MOD;
            big_c[i][j] = num*fpow(kf,MOD-2)%MOD;
        }
    } 
    assert(m <= 1010);
    rep(j,1,m){
        rep(p,0,2) rep(num,1,n+1){
            T cur = 0;
            rep(l,1+p,num+1){
                cur = (cur+fC(num-1-p,l-1-p)*big_c[j][l]%MOD)%MOD;
            } 
            pre[j][p][num] = cur;
        } 
    }
    
    T ans = 0; 
    rep(i,1,n+1){
        rep(j,lft[i],rit[i]+1){
            // fix first one we use same group j
            int num_with = 0;
            for(int k = i; k >= 1; k--)if(lft[k] <= j && j <= rit[k]){
                num_with++;
                dp[i][j] = (dp[i][j]+pre[j][k!=i][num_with]*dp[k-1][j-1]%MOD)%MOD;
            }
            ans = (ans+dp[i][j])%MOD;
        }
        // build psa
        rep(j,1,m){
            dp[i][j] = (dp[i][j]+dp[i][j-1])%MOD;
        }
        rep(j,0,m){
            dp[i][j] = (dp[i][j]+dp[i-1][j])%MOD;
        }
    }
    cout << ans << "\n";
}

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