Submission #624365

#TimeUsernameProblemLanguageResultExecution timeMemory
624365socpiteBoat (APIO16_boat)C++14
9 / 100
1133 ms12444 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; const int maxn = 1005; const int mod = 1e9+7; int n; pair<int, int> A[maxn]; vector<int> cp; ll dp[maxn][2*maxn], pc[2*maxn][maxn], inv[maxn]; int main(){ inv[0] = inv[1] = 1; for(int i = 2; i < maxn; i++)inv[i]=mod - inv[mod%i]*(mod/i)%mod; cin >> n; for(int i = 1; i <= n; i++){ cin >> A[i].f >> A[i].s; cp.push_back(A[i].f-1); cp.push_back(A[i].s); } cp.push_back(0); sort(cp.begin(), cp.end()); cp.erase(unique(cp.begin(), cp.end()), cp.end()); for(int i = 1; i < cp.size(); i++){ ll len = cp[i]-cp[i-1]; pc[i][1] = len; for(int j = 2; j <= n; j++){ ll crr = len*(len-1)/2; crr%=mod; for(int k = 2; k <= min({n, int(len), j}); k++){ pc[i][j] += crr; // C(k-2, j)*C(k, len) if(pc[i][j] >= mod)pc[i][j]-=mod; k-=2; crr=crr*(j-k)%mod; crr=crr*inv[k+1]%mod; k+=2; crr=crr*(len-k)%mod; crr=crr*inv[k+1]%mod; } } } for(int i = 0; i < cp.size(); i++)dp[0][i]=1; for(int i = 0; i <= n; i++)dp[i][0]=1; for(int i = 1; i <= n; i++){ for(int j = 1; j < cp.size(); j++){ if(A[i].f > cp[j] || A[i].s <= cp[j-1])dp[i][j]=0; else{ int cnt = 0; for(int k = i; k > 0; k--){ if(A[k].s >= cp[j] && A[k].f <= cp[j-1]+1){ cnt++; dp[i][j]+=dp[k-1][j-1]*pc[j][cnt]%mod; dp[i][j]%=mod; } } } dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; dp[i][j]%=mod; } } ll ans = dp[n][cp.size()-1]-1; ans%=mod; if(ans < 0)ans+=mod; cout << ans; }

Compilation message (stderr)

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