Submission #260470

#	Time	Username	Problem	Language	Result	Execution time	Memory
260470		shayan_p	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	370 ms	14764 KiB

ruins3

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1220, mod = 1e9 + 7, inf = 1e9 + 10;

int dp[maxn][maxn], C[maxn][maxn];
bool is[maxn];

int dp2[maxn][maxn], F[maxn];

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

    for(int i = 0; i < maxn; i++){
	C[i][i] = C[i][0] = 1;
	for(int j = 1; j < i; j++)
	    C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
    }

    dp2[0][0] = 1;    
    for(int i = 1; i < maxn; i++){
	for(int j = 0; j <= i; j++){
	    if(j + 2 <= i)
		dp2[i][j] = (1ll * dp2[i][j] + 1ll * C[i-j][2] * dp2[i-1][j+1]) % mod;
	    if(j >= 1)
		dp2[i][j] = (1ll * dp2[i][j] + 1ll * C[i+j][2] * dp2[i-1][j-1]) % mod;
	    if(j < i)
		dp2[i][j] = (1ll * dp2[i][j] + 1ll * (i-j) * (i+j) % mod * dp2[i-1][j]) % mod;
	}
    }

    for(int i = 1; i < maxn; i++){
	F[i] = dp2[i][0];
	for(int j = 1; j < i; j++){
	    F[i] = (1ll * F[i] - 1ll * C[i-1][j-1] %mod * C[i][j] %mod * F[j] % mod * dp2[i-j][0]) % mod;
	}
	F[i] = (F[i] + mod) % mod;
    }
    
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
	int x;
	cin >> x;
	is[x] = 1;
    }
    int cnt = 0;
    for(int i = 2*n; i >= 1; i--){
	cnt+= is[i] ? 1 : -1;
	if(cnt < 0)
	    return cout << 0 << endl, 0;
    }
    
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
	int A = 0, B = 0;
	for(int j = 2*n; j >= 1; j--){
	    if(is[j]){
		if(++A == i)
		    break;
	    }
	    else{
		++B;
	    }
	}
	for(int j = i; j >= 0; j--){
	    if(B > i-j)
		continue;
	    int extra = i-j - B;
	    if(j > 0)
		dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
	    for(int k = 1; k + j <= i && k <= extra; k++){
		dp[i][j] = (1ll * dp[i][j] + 1ll * C[j + k-1][k-1] * F[k] % mod * C[extra][k] % mod * dp[i-1][j + k-1]) % mod;
	    }
	}
    }
    return cout << dp[n][0] << endl, 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42