oj.uz

Submission #230603

# Submission time Handle Problem Language Result Execution time Memory
230603 2020-05-10T14:44:29 Z brcode Boat (APIO16_boat) C++14
0 / 100
 294 ms 4472 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MAXN = 500;
long long a[MAXN];
long long b[MAXN];
long long dp[MAXN][MAXN];
long long fac[4*MAXN];
vector<long long> pts;
long long power(long long x, long long y, long long p) { 
    long long res = 1;      
  
    x = x % p;  
  
    while (y > 0) 
    { 
        
        if (y & 1) 
            res = (res*x) % p; 
  
        
        y = y>>1;
        x = (x*x) % p; 
    } 
    return res; 
} 
  
long long modInverse(long long n, long long p) { 
    return power(n, p-2, p); 
} 
   
long long nCrModPFermat(long long n, long long r) { 
   long long p = MOD;
    
   
   if (r==0) 
      return 1;
   
   
  
    return (1LL*fac[n]* modInverse(fac[r], p) % p * 
            1LL*modInverse(fac[n-r], p) % p) % p; 
} 
int main() {
    long long n;
    cin>>n;
    fac[0] = 1;
    for(long long i=1;i<=1000;i++){
        fac[i] = (1LL*fac[i-1]*i)%MOD; 
        
    }
    
    for(long long 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(long long i=0;i<pts.size();i++){
       
        dp[0][i] = 1;
    }
    for(long long i=1;i<=n;i++){
        dp[i][0] = 1;
        for(long long j=1;j<pts.size();j++){
            dp[i][j] = dp[i][j-1];
            
            long long cnt = 0;
            for(long long k=i;k>=1;k--){
                if(a[k-1]<pts[j] && b[k-1]>=pts[j]){
                    cnt++;
                    dp[i][j]+=(1LL*dp[k-1][j-1]*nCrModPFermat(pts[j]-pts[j-1]+cnt-1,cnt));
                    dp[i][j]%=MOD;
                    if(i==2 && j==2){
                      //  cout<<k<<" "<<dp[i][j]<<" "<<pts[j]-pts[j-1]<<" "<<cnt<<endl;
                    }
                  // cout<<pts[j]-pts[j-1]<<" "<<cnt<<" "<<nCrModPFermat(pts[j]-pts[j-1],cnt)<<endl;
                }
            }
           // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }
    cout<<dp[n][pts.size()-1]-1<<endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:63:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:69:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(long long j=1;j<pts.size();j++){
                           ~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -