Contest Duration: ~ (local time) (150 minutes) Back to Home

Submission #5970874

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 610;
const int mod = 1e9 + 7;
long long dp[maxn][maxn] = {0}, g[maxn], h[maxn][maxn];
int ea[maxn], eb[maxn];
int n, m;
bool in(int l, int r, int x)
{
return l <= x && x <= r;
}
int get(int l, int r)
{
int cnt = 0;
for(int i = 1; i <= m; i ++)
{
bool asd1 = in(l, r, ea[i]), asd2 = in(l, r, eb[i]);
if(asd1 ^ asd2)
return -1;
if(asd1)
cnt ++;
}
return cnt * 2;
}
int main()
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
n *= 2;
for(int i = 1; i <= m; i ++)
cin >> ea[i] >> eb[i];
g[0] = 1;
for(int i = 2; i <= n; i += 2)
g[i] = g[i - 2] * (i - 1) % mod;
for(int i = 1; i <= n; i ++)
for(int j = i; j <= n; j ++)
h[i][j] = get(i, j);
long long ans = 0;
for(int l = 2; l <= n; l += 2)
for(int i = 1; i + l - 1 <= n; i ++)
{
int j = i + l - 1;
//cout << i << " " << j << " : " << endl;
int c = h[i][j];
//cout << c << endl;
if(c != -1)
{
long long a = g[n - l - m * 2 + c];
dp[i][j] = g[l - c] % mod;
//cout << g[l - c] << " " << a << endl;
for(int k = i + 1; k < j; k += 2)
if(h[k + 1][j] != -1 && h[i][k] != -1)
{
(dp[i][j] += (mod - dp[i][k] * g[j - k - h[k + 1][j]] % mod)) %= mod;
//cout << k << " " << dp[i][k] << " " << j - k - h[k + 1][j] << " " << g[j - k - 1 - h[k + 1][j]] << endl;
//cout << dp[i][k] * g[j - k - 1 - h[k + 1][j]] % mod * a % mod << endl;
}
(ans += dp[i][j] * a) %= mod;
}
//cout << dp[i][j] << endl;
}
cout << ans << endl;
return 0;
}```

#### Submission Info

Submission Time 2019-06-16 21:42:10+0900 D - Chords zhangyuxi C++14 (GCC 5.4.1) 900 1705 Byte AC 104 ms 6016 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
sample-01.txt 2 ms 2304 KB
sample-02.txt 2 ms 2304 KB
sample-03.txt 2 ms 2432 KB