Submission #118609

#TimeUsernameProblemLanguageResultExecution timeMemory
118609pzdbaBoat (APIO16_boat)C++14
100 / 100
576 ms4512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9+7; vector<int> h; int a[505], b[505], l[1005]; LL dp[505][1005]; LL inv[505]; LL go(LL a, LL b){ LL ans=1; while(b){ if(b%2) ans=ans*a%mod; a=a*a%mod; b/=2; } return ans; } int main(){ int n; scanf("%d", &n); for(int i=0;i<=n;i++) inv[i] = go(i, mod-2); for(int i=1;i<=n;i++){ scanf("%d%d", &a[i], &b[i]); h.push_back(a[i]-1); h.push_back(b[i]); } sort(h.begin(), h.end()); h.erase(unique(h.begin(), h.end()), h.end()); for(int i=1;i<=n;i++){ a[i] = lower_bound(h.begin(), h.end(), a[i]-1) - h.begin() + 1; b[i] = lower_bound(h.begin(), h.end(), b[i]) - h.begin() + 1; } l[1] = h[0]; for(int i=2;i<=h.size();i++) l[i] = h[i-1] - h[i-2]; for(int i=1;i<=n;i++){ for(int j=1;j<=h.size();j++){ if(i == 1){ if(a[i] < j && j <= b[i]) dp[i][j] = (dp[i][j] + l[j])%mod; } else{ if(a[i] < j && j <= b[i]){ dp[i][j] = (dp[i][j] + l[j] + l[j]*dp[i-1][j-1])%mod; int cnt = 1; LL sum = l[j]-1; for(int k=i-1;k>=1;k--){ if(a[k] < j && j <= b[k]){ cnt++; sum = sum*(l[j]+cnt-2)%mod*inv[cnt]%mod; dp[i][j] = (dp[i][j] + sum + sum*dp[k-1][j-1])%mod; } } } } dp[i][j] = (dp[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mod)%mod; } } printf("%lld\n", dp[n][h.size()]); }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<=h.size();i++) l[i] = h[i-1] - h[i-2];
                 ~^~~~~~~~~~
boat.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<=h.size();j++){
                     ~^~~~~~~~~~
boat.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:25: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]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...