| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1020791 |
2024-07-12T09:57:19 Z |
flappybird |
Boat (APIO16_boat) |
C++17 |
|
1380 ms |
8276 KB |
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 510
#define MAXQ 101010
#define INF 1000000100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
int A[MAX];
int B[MAX];
int sz[MAX];
ll C[MAX * 2][MAX];
ll dp[MAX][MAX * 2];
ll mpow(ll x, ll y = MOD - 2) {
if (!y) return 1;
ll res = mpow(x, y >> 1);
res *= res;
res %= MOD;
if (y & 1) res = (res * x) % MOD;
return res;
}
ll rev[MAX * 2];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i, j, k;
vector<int> v;
for (i = 1; i <= N; i++) {
cin >> A[i] >> B[i];
B[i]++;
v.push_back(A[i]);
v.push_back(B[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (i = 1; i <= N; i++) {
A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
B[i] = lower_bound(v.begin(), v.end(), B[i]) - v.begin();
}
for (i = 1; i <= N * 2; i++) rev[i] = mpow(i);
int X = v.size() - 1;
for (i = 0; i < X; i++) {
sz[i] = v[i + 1] - v[i];
for (j = 1; j <= N; j++) {
ll c1, c2;
c1 = 1;
c2 = sz[i];
C[i][j] += c1 * c2;
C[i][j] %= MOD;
for (k = 0; k < j - 1; k++) {
c1 *= j - 1 - k;
c1 %= MOD;
c1 *= rev[k + 1];
c1 %= MOD;
c2 *= sz[i] - (k + 1);
c2 %= MOD;
c2 *= rev[k + 2];
c2 %= MOD;
C[i][j] += c1 * c2;
C[i][j] %= MOD;
}
}
}
for (i = 1; i <= N; i++) {
int cnt = 1;
if (A[i] == 0) {
for (j = 1; j < i; j++) if (A[j] == 0) cnt++;
dp[i][0] += C[0][cnt];
}
for (j = 1; j < X; j++) {
dp[i][j] = dp[i][j - 1];
if (B[i] <= j) continue;
if (j < A[i]) continue;
cnt = 1;
for (k = i - 1; k >= 1; k--) {
dp[i][j] += C[j][cnt] * dp[i - 1][j - 1];
dp[i][j] %= MOD;
if (A[k] <= j && j < B[k]) cnt++;
}
dp[i][j] += C[j][cnt];
}
}
ll ans = 0;
for (i = 1; i <= N; i++) ans = (ans + dp[i][X - 1]) % MOD;
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1380 ms |
8276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1380 ms |
8276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1380 ms |
8276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
