제출 #793051

#제출 시각아이디문제언어결과실행 시간메모리
793051algorithm16Boat (APIO16_boat)C++14
100 / 100
1606 ms15188 KiB
#include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n,a[505],b[505],dp[1505][2][505][2],inv[505],m[1505][505],mod=1e9+7; vector <int> v,v1; vector <vector<int> > v2; int sum(int a,int b) { return (a+b)%mod; } int mul(int a,int b) { return ((long long)a*b)%mod; } int exp(int a,int b) { if(!b) return 1; int ret=exp(a,b/2); if(b%2==0) return mul(ret,ret); return mul(mul(ret,ret),a); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i=0;i<n;i++) { cin >> a[i] >> b[i]; v.push_back(a[i]); v.push_back(b[i]); v.push_back(b[i]+1); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); /*for(int i=0;i<v.size()-1;i++) { cout << v[i] << " " << v[i+1]-1 << "\n"; }*/ /*for(int i=0;i<n;i++) { a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin(); b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin(); }*/ for(int i=1;i<=n;i++) { inv[i]=exp(i,mod-2); } for(int i=0;i<v.size()-1;i++) { for(int j=0;j<=n;j++) { dp[i][n%2][j][0]=1; dp[i][n%2][j][1]=1; } } for(int i=0;i<v.size()-1;i++) { for(int j=0;j<n;j++) { m[i][j]=mul(v[i+1]-v[i]-j,inv[j+1]); } } for(int x=n-1;x>=0;x--) { for(int idx=v.size()-2;idx>=0;idx--) { for(int cnt=0;cnt<=x;cnt++) { for(int a1=0;a1<2;a1++) { int ret=0; if(!a1) ret=dp[idx][(x+1)%2][cnt][0]; // 0 if(v[idx]>=a[x] && v[idx+1]-1<=b[x]) { if(cnt<=v[idx+1]-1-v[idx]) ret+=mul(dp[idx][(x+1)%2][cnt+1][0],m[idx][cnt]); } if(ret>=mod) ret-=mod; ret+=dp[idx+1][x%2][0][1]; if(ret>=mod) ret-=mod; dp[idx][x%2][cnt][a1]=ret; //cout << idx << " " << x << " " << cnt << " " << a1 << " " << ret << "\n"; } } } } cout << dp[0][0][0][0]-1; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<v.size()-1;i++) {
      |              ~^~~~~~~~~~~
boat.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<v.size()-1;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...