Submission #792984

#TimeUsernameProblemLanguageResultExecution timeMemory
792984algorithm16Boat (APIO16_boat)C++14
27 / 100
1237 ms524288 KiB
#include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n,dp[1505][505][505],a[505],b[505],inv[505],mod=1e9+7; vector <int> v; 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 rec(int idx,int x,int cnt) { if(idx>=v.size()-1) return 0; if(x>=n) return 1; if(dp[idx][x][cnt]!=-1) return dp[idx][x][cnt]; int ret=0; ret=sum(ret,rec(idx,x+1,cnt)); // 0 //if(idx==0 && x==1 && cnt==1) cout << ret << "\n"; if(v[idx]>=a[x] && v[idx+1]-1<=b[x]) { if(cnt<=v[idx+1]-1-v[idx]) ret=sum(ret,mul(rec(idx,x+1,cnt+1),mul(v[idx+1]-v[idx]-cnt,inv[cnt+1]))); } for(int i=idx+1;i<v.size()-1;i++) { if(v[i]>=a[x] && v[i+1]-1<=b[x]) ret=sum(ret,mul(rec(i,x+1,1),v[i+1]-v[i])); } dp[idx][x][cnt]=ret; //cout << idx << " " << x << " " << cnt << " " << ret << "\n"; return ret; } 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=0;i<v.size()-1;i++) { for(int j=0;j<n;j++) { for(int k=0;k<=j;k++) { dp[i][j][k]=-1; } } } for(int i=1;i<=n;i++) { inv[i]=exp(i,mod-2); } cout << rec(0,0,0)-1; return 0; }

Compilation message (stderr)

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