| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 258576 | 2020-08-06T07:23:35 Z | daniel920712 | Boat (APIO16_boat) | C++14 | 2000 ms | 7672 KB |
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <time.h>
using namespace std;
long long MOD=1e9+7;
long long DP[505][2005];
long long CCon[505];
long long Con2[505];
bool use[505][2005]={0};
long long cha[2005],Con[2005],R[2005];
map < long long , long long > all;
long long N,now=0;
long long a[505],b[505];
map < long long , long long > con,r;
set < long long > have;
long long Pow(long long a,long long b)
{
if(b==0) return 1;
long long t=Pow(a,b/2);
t*=t;
t%=MOD;
if(b%2) t*=a;
return t%MOD;
}
long long C(long long x,long long y)
{
return CCon[x]*Con2[y]%MOD*Con2[x-y]%MOD;
}
long long F(long long x,long long y)
{
long long i,j,k,tt,ttt=0,aa=1;
if(x==0) return y!=(now);
if(use[x][y]) return DP[x][y];
use[x][y]=1;
DP[x][y]=F(x-1,y);
for(i=0;i<now;i++)
{
ttt=0;
if(!(cha[i]>=a[x]&&R[i]<cha[y]&&R[i]<=b[x])) continue;
ttt=0;
DP[x][y]+=Con[i]*F(x-1,i)%MOD;
DP[x][y]%=MOD;
for(j=x;j>=1;j--)
{
if(cha[i]>=a[j]&&R[i]<cha[y]&&R[i]<=b[j])
{
ttt++;
aa=Con[i];
for(k=2;k<=ttt;k++)
{
aa*=(Con[i]-k+1);
aa%=MOD;
aa*=Pow(k,MOD-2);
aa%=MOD;
aa*=C(ttt-2,k-2);
aa%=MOD;
if(aa==0) break;
DP[x][y]+=aa*F(j-1,i)%MOD;
DP[x][y]%=MOD;
}
}
}
}
return DP[x][y];
}
int main()
{
//freopen("3_01.in","rt",stdin);
long long N,M,i;
scanf("%lld",&N);
CCon[0]=1;
Con2[0]=1;
for(i=1;i<=N;i++)
{
CCon[i]=CCon[i-1]*i%MOD;
Con2[i]=Pow(CCon[i],MOD-2);
}
for(i=1;i<=N;i++)
{
scanf("%lld %lld",&a[i],&b[i]);
have.insert(a[i]);
have.insert(a[i]+1);
have.insert(b[i]);
have.insert(b[i]+1);
}
for(auto i:have)
{
if(i==*prev(have.end()))
{
con[i]=1;
r[i]=i;
}
if(have.lower_bound(i)!=have.begin())
{
con[*prev(have.lower_bound(i))]=i-*prev(have.lower_bound(i));
r[*prev(have.lower_bound(i))]=i-1;
}
}
for(auto i:con)
{
cha[now]=i.first;
Con[now]=i.second;
R[now]=r[i.first];
now++;
}
cha[now]=1e9+5;
Con[now]=0;
R[now]=2e9;
printf("%lld\n",F(N,now));
return 0;
}
/*
2
32 47
18 78
*/
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 187 ms | 7416 KB | Output is correct |
| 2 | Correct | 191 ms | 7416 KB | Output is correct |
| 3 | Correct | 183 ms | 7544 KB | Output is correct |
| 4 | Correct | 184 ms | 7672 KB | Output is correct |
| 5 | Correct | 192 ms | 7584 KB | Output is correct |
| 6 | Correct | 195 ms | 6392 KB | Output is correct |
| 7 | Correct | 216 ms | 6192 KB | Output is correct |
| 8 | Correct | 206 ms | 6820 KB | Output is correct |
| 9 | Correct | 219 ms | 6624 KB | Output is correct |
| 10 | Correct | 223 ms | 6840 KB | Output is correct |
| 11 | Correct | 204 ms | 6544 KB | Output is correct |
| 12 | Correct | 203 ms | 7288 KB | Output is correct |
| 13 | Correct | 197 ms | 6780 KB | Output is correct |
| 14 | Correct | 200 ms | 6272 KB | Output is correct |
| 15 | Correct | 207 ms | 6904 KB | Output is correct |
| 16 | Correct | 70 ms | 4088 KB | Output is correct |
| 17 | Correct | 65 ms | 4088 KB | Output is correct |
| 18 | Correct | 56 ms | 4088 KB | Output is correct |
| 19 | Correct | 82 ms | 4216 KB | Output is correct |
| 20 | Correct | 59 ms | 4088 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 187 ms | 7416 KB | Output is correct |
| 2 | Correct | 191 ms | 7416 KB | Output is correct |
| 3 | Correct | 183 ms | 7544 KB | Output is correct |
| 4 | Correct | 184 ms | 7672 KB | Output is correct |
| 5 | Correct | 192 ms | 7584 KB | Output is correct |
| 6 | Correct | 195 ms | 6392 KB | Output is correct |
| 7 | Correct | 216 ms | 6192 KB | Output is correct |
| 8 | Correct | 206 ms | 6820 KB | Output is correct |
| 9 | Correct | 219 ms | 6624 KB | Output is correct |
| 10 | Correct | 223 ms | 6840 KB | Output is correct |
| 11 | Correct | 204 ms | 6544 KB | Output is correct |
| 12 | Correct | 203 ms | 7288 KB | Output is correct |
| 13 | Correct | 197 ms | 6780 KB | Output is correct |
| 14 | Correct | 200 ms | 6272 KB | Output is correct |
| 15 | Correct | 207 ms | 6904 KB | Output is correct |
| 16 | Correct | 70 ms | 4088 KB | Output is correct |
| 17 | Correct | 65 ms | 4088 KB | Output is correct |
| 18 | Correct | 56 ms | 4088 KB | Output is correct |
| 19 | Correct | 82 ms | 4216 KB | Output is correct |
| 20 | Correct | 59 ms | 4088 KB | Output is correct |
| 21 | Execution timed out | 2083 ms | 1940 KB | Time limit exceeded |
| 22 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2090 ms | 888 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 187 ms | 7416 KB | Output is correct |
| 2 | Correct | 191 ms | 7416 KB | Output is correct |
| 3 | Correct | 183 ms | 7544 KB | Output is correct |
| 4 | Correct | 184 ms | 7672 KB | Output is correct |
| 5 | Correct | 192 ms | 7584 KB | Output is correct |
| 6 | Correct | 195 ms | 6392 KB | Output is correct |
| 7 | Correct | 216 ms | 6192 KB | Output is correct |
| 8 | Correct | 206 ms | 6820 KB | Output is correct |
| 9 | Correct | 219 ms | 6624 KB | Output is correct |
| 10 | Correct | 223 ms | 6840 KB | Output is correct |
| 11 | Correct | 204 ms | 6544 KB | Output is correct |
| 12 | Correct | 203 ms | 7288 KB | Output is correct |
| 13 | Correct | 197 ms | 6780 KB | Output is correct |
| 14 | Correct | 200 ms | 6272 KB | Output is correct |
| 15 | Correct | 207 ms | 6904 KB | Output is correct |
| 16 | Correct | 70 ms | 4088 KB | Output is correct |
| 17 | Correct | 65 ms | 4088 KB | Output is correct |
| 18 | Correct | 56 ms | 4088 KB | Output is correct |
| 19 | Correct | 82 ms | 4216 KB | Output is correct |
| 20 | Correct | 59 ms | 4088 KB | Output is correct |
| 21 | Execution timed out | 2083 ms | 1940 KB | Time limit exceeded |
| 22 | Halted | 0 ms | 0 KB | - |