Submission #51625

#TimeUsernameProblemLanguageResultExecution timeMemory
51625tmwilliamlin168Boat (APIO16_boat)C++14
100 / 100
702 ms8700 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mxN=500, M=1e9+7; int n, a[mxN], b[mxN]; ll dp[mxN+1][2*mxN], c[2*mxN][mxN+1], mi[mxN+1]; vector<int> pts; inline ll modI(ll a, ll m) { return a<=1?a:(1-modI(m%a, a)*m)/a+m; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i<n; ++i) { cin >> a[i] >> b[i], --a[i]; pts.push_back(a[i]); pts.push_back(b[i]); } sort(pts.begin(), pts.end()); pts.resize(unique(pts.begin(), pts.end())-pts.begin()); for(int i=2; i<=n; ++i) mi[i]=modI(i, M); for(int i=1; i<pts.size(); ++i) { c[i][1]=pts[i]-pts[i-1]; for(int j=2; j<=n; ++j) c[i][j]=c[i][j-1]*(pts[i]-pts[i-1]+j-1)%M*mi[j]%M; } for(int i=0; i<pts.size(); ++i) dp[0][i]=1; for(int i=1; i<=n; ++i) { dp[i][0]=1; for(int j=1; j<pts.size(); ++j) { dp[i][j]=dp[i][j-1]; for(int k=i, n2=0; k; --k) { if(pts[j]>a[k-1]&&pts[j]<=b[k-1]) { ++n2; dp[i][j]+=dp[k-1][j-1]*c[j][n2]%M; } } dp[i][j]%=M; } } cout << dp[n][pts.size()-1]-1; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<pts.size(); ++i) {
               ~^~~~~~~~~~~
boat.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<pts.size(); ++i)
               ~^~~~~~~~~~~
boat.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1; j<pts.size(); ++j) {
                ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...