이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1000;
const ll MOD = 1e9+7;
int N, S, A[MAXN+10], B[MAXN+10];
vector<int> comp;
ll inv[MAXN+10], bino[MAXN+10][MAXN+10], comb[MAXN+10], f[MAXN+10];
ll dp[MAXN+10][MAXN+10], ans;
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin(); }
ll mypow(ll x, ll y)
{
if(y==0) return 1;
if(y%2) return mypow(x, y-1)*x%MOD;
ll t=mypow(x, y/2);
return t*t%MOD;
}
int main()
{
int i, j, k;
bino[0][0]=1;
for(i=1; i<=MAXN; i++) for(j=0; j<=i; j++)
{
if(j==0 || j==i) bino[i][j]=1;
else bino[i][j]=(bino[i-1][j]+bino[i-1][j-1])%MOD;
}
inv[0]=1;
for(i=1; i<=MAXN; i++) inv[i]=mypow(i, MOD-2);
scanf("%d", &N);
for(i=1; i<=N; i++)
{
scanf("%d%d", &A[i], &B[i]); B[i]++;
comp.push_back(A[i]);
comp.push_back(B[i]);
}
comp.push_back(0);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
S=comp.size()-2;
ll a=comp[2]-comp[1];
memset(comb, 0, sizeof(comb)); memset(f, 0, sizeof(f));
comb[0]=1;
for(j=1; j<=a; j++) comb[j]=comb[j-1]*(a-j+1)%MOD*inv[j]%MOD;
for(j=1; j<=N; j++)
{
for(k=1; k<=j; k++)
{
f[j]+=comb[k]*bino[j-1][k-1]%MOD;
f[j]%=MOD;
}
}
int cnt=0;
for(i=1; i<=N; i++)
{
if(!(A[i]<=comp[1] && comp[1]<B[i])) continue;
cnt++;
dp[i][1]=f[cnt];
}
dp[0][1]=1;
for(i=2; i<=S; i++)
{
dp[0][i]=1;
a=comp[i+1]-comp[i];
memset(comb, 0, sizeof(comb)); memset(f, 0, sizeof(f));
comb[0]=1;
for(j=1; j<=min(600ll, a); j++) comb[j]=comb[j-1]*(a-j+1)%MOD*inv[j]%MOD;
for(j=1; j<=N; j++)
{
for(k=1; k<=j; k++)
{
f[j]+=comb[k]*bino[j-1][k-1]%MOD;
f[j]%=MOD;
}
}
for(j=1; j<=N; j++)
{
if(!(A[j]<=comp[i] && comp[i]<B[j])) { dp[j][i]=dp[j][i-1]; continue; }
int cnt=1;
for(k=j-1; k>=0; k--)
{
dp[j][i]+=f[cnt]*dp[k][i-1]%MOD;
dp[j][i]%=MOD;
if(A[k]<=comp[i] && comp[i]<B[k]) cnt++;
}
dp[j][i]+=dp[j][i-1]; dp[j][i]%=MOD;
}
}
//for(i=1; i<=N; i++) { for(j=1; j<=S; j++) printf("%lld ", dp[i][j]-dp[i][j-1]); printf("\n"); }
for(i=1; i<=N; i++) ans+=dp[i][S], ans%=MOD;
printf("%lld", ans);
}
컴파일 시 표준 에러 (stderr) 메시지
boat.cpp: In function 'int main()':
boat.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
boat.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]); B[i]++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |