제출 #153028

#제출 시각아이디문제언어결과실행 시간메모리
153028arnold518Boat (APIO16_boat)C++14
31 / 100
993 ms14588 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...