# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
184091 | dndhk | Boat (APIO16_boat) | C++14 | 2080 ms | 6392 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll MOD = 1000000007;
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500;
int N, M;
int a[MAX_N+1], b[MAX_N+1];
vector<int> v1;
vector<ll> v;
map<int, int> mp;
void input(){
scanf("%d", &N);
for(int i=1 ;i<=N; i++){
scanf("%d%d", &a[i], &b[i]);
b[i]++;
v1.pb(a[i]); v1.pb(b[i]);
}
sort(v1.begin(), v1.end());
v1.erase(unique(v1.begin(), v1.end()), v1.end());
sort(v1.begin(), v1.end());
v.pb(1LL);
for(int i=0; i<v1.size()-1; i++){
mp[v1[i]] = v.size();
v.pb(v1[i+1]-v1[i]);
}mp[v1.back()] = v.size();
for(int i=1; i<=N; i++){
a[i] = mp[a[i]]; b[i] = mp[b[i]]-1;
}
M = v.size()-1;
}
ll multi(ll x, ll y){
if(y==0){
return 1LL;
}if(y==1){
return x%MOD;
}
ll m = multi(x, y/2);
if(y%2){
return ((m*m%MOD)*x)%MOD;
}
return (m*m)%MOD;
}
ll inv[MAX_N+1];
ll dp[MAX_N*2+1][MAX_N+1];
ll dp2[MAX_N+1][MAX_N+1];
void solve(){
for(int i=1; i<=N; i++){
inv[i] = multi((ll)i, MOD-2);
}
for(int i=0; i<=M; i++) dp[i][0] = 1LL;
for(int i=1; i<=N; i++) dp[0][i] = 1LL;
for(int k=1; k<=M; k++){
for(int i=1; i<=N; i++){
dp2[i][1] = dp2[i-1][1];
if(a[i]<=k && k<=b[i]) dp2[i][1] = (dp2[i][1] + (dp[k-1][i-1] * v[k] % MOD)) % MOD;
dp[k][i]=dp2[i][1];
for(int j=2; j<=N; j++){
dp2[i][j] = dp2[i-1][j];
if(a[i]<=k && k<=b[i]) dp2[i][j] = (dp2[i][j] + ((dp2[i-1][j-1] * (max(0LL, v[k]-(ll)(j-1)))%MOD) * inv[j] % MOD)) % MOD;
dp[k][i] = (dp[k][i] + dp2[i][j]) % MOD;
}
dp[k][i] = (dp[k][i] + dp[k-1][i]) % MOD;
}
}
}
int main(){
input();
solve();
cout<<(dp[M][N]+MOD-1) % MOD;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |