# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
139298 | 3zp | Boat (APIO16_boat) | C++14 | 15 ms | 6264 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5009], b[5009];
ll mod = 1e9+7;
ll c[2009];
ll l[5009], r[5009];
ll dp[5009][4009];
ll in[5009];
vector<pair<ll,ll> > d;
main(){
ll n;
cin >> n;
for(ll i = 0; i < n; i++){
cin >> a[i] >> b[i];
c[2*i] = a[i];
c[2*i + 1] = b[i];
}
sort(c, c+2*n);
in[0] = 1;
in[1] = 1;
for (ll i = 2; i <= n; i++)
in[i] = in[mod % i] *(mod - mod / i) % mod;
for(ll i = 0; i < 2*n; i++){
if(i < 2*n-1 && c[i] == c[i+1]) continue;
d.push_back({c[i], c[i]});
if(i == 2*n-1 || c[i+1] == c[i]+1) continue;
d.push_back({c[i]+1, c[i+1]-1});
}
for (ll i= 0; i < n; i++){
for (ll j = 0; j < d.size(); j++){
if(a[i] == d[j].first) {l[i] = j; break;}
}
for (ll j = 0; j < d.size(); j++){
if(b[i] == d[j].second) r[i] = j;
}
}
ll N = d.size();
for(ll i = 0; i < n; i++){
for(ll j = 0; j < N; j++){
if(j) dp[i][j] = (dp[i][j-1]);
else dp[i][j] = 1;
ll L = d[j].second - d[j].first + 1;
ll W = 1;
for (ll t = i; t >= 0; t--){
if(l[t] > j || r[t] < j) break;
W = (W*(L - (i -t)) % mod )*in[i-t+1] % mod;
if(!W) break;
if(t == 0) dp[i][j] = (dp[i][j] + W) % mod; else
if(j == 0) dp[i][j] = (dp[i][j] + W) % mod; else
dp[i][j] = (dp[i][j] + W*dp[t-1][j-1]) % mod;
}
}
for(ll j = 0; j < N; j++){
if(i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
else dp[i][j] = (dp[i][j] + 1) % mod;
}
}
cout << (dp[n-1][N-1] -1 + mod)% mod << endl;
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... |