oj.uz

Submission #230605

# Submission time Handle Problem Language Result Execution time Memory
230605 2020-05-10T14:46:15 Z brcode Boat (APIO16_boat) C++14
9 / 100
 2000 ms 4472 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MAXN = 1000;
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() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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:65:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:71:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(long long j=1;j<pts.size();j++){
                           ~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 4344 KB Output is correct
2 Correct 353 ms 4344 KB Output is correct
3 Correct 351 ms 4344 KB Output is correct
4 Correct 344 ms 4472 KB Output is correct
5 Correct 348 ms 4424 KB Output is correct
6 Correct 253 ms 4344 KB Output is correct
7 Correct 245 ms 4348 KB Output is correct
8 Correct 244 ms 4348 KB Output is correct
9 Correct 256 ms 4344 KB Output is correct
10 Correct 251 ms 4344 KB Output is correct
11 Correct 254 ms 4344 KB Output is correct
12 Correct 251 ms 4344 KB Output is correct
13 Correct 239 ms 4344 KB Output is correct
14 Correct 244 ms 4344 KB Output is correct
15 Correct 252 ms 4472 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 112 ms 3064 KB Output is correct
18 Correct 112 ms 3064 KB Output is correct
19 Correct 114 ms 3172 KB Output is correct
20 Correct 114 ms 3068 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 4344 KB Output is correct
2 Correct 353 ms 4344 KB Output is correct
3 Correct 351 ms 4344 KB Output is correct
4 Correct 344 ms 4472 KB Output is correct
5 Correct 348 ms 4424 KB Output is correct
6 Correct 253 ms 4344 KB Output is correct
7 Correct 245 ms 4348 KB Output is correct
8 Correct 244 ms 4348 KB Output is correct
9 Correct 256 ms 4344 KB Output is correct
10 Correct 251 ms 4344 KB Output is correct
11 Correct 254 ms 4344 KB Output is correct
12 Correct 251 ms 4344 KB Output is correct
13 Correct 239 ms 4344 KB Output is correct
14 Correct 244 ms 4344 KB Output is correct
15 Correct 252 ms 4472 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 112 ms 3064 KB Output is correct
18 Correct 112 ms 3064 KB Output is correct
19 Correct 114 ms 3172 KB Output is correct
20 Correct 114 ms 3068 KB Output is correct
21 Execution timed out 2074 ms 2136 KB Time limit exceeded
22 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 Correct 360 ms 4344 KB Output is correct
2 Correct 353 ms 4344 KB Output is correct
3 Correct 351 ms 4344 KB Output is correct
4 Correct 344 ms 4472 KB Output is correct
5 Correct 348 ms 4424 KB Output is correct
6 Correct 253 ms 4344 KB Output is correct
7 Correct 245 ms 4348 KB Output is correct
8 Correct 244 ms 4348 KB Output is correct
9 Correct 256 ms 4344 KB Output is correct
10 Correct 251 ms 4344 KB Output is correct
11 Correct 254 ms 4344 KB Output is correct
12 Correct 251 ms 4344 KB Output is correct
13 Correct 239 ms 4344 KB Output is correct
14 Correct 244 ms 4344 KB Output is correct
15 Correct 252 ms 4472 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 112 ms 3064 KB Output is correct
18 Correct 112 ms 3064 KB Output is correct
19 Correct 114 ms 3172 KB Output is correct
20 Correct 114 ms 3068 KB Output is correct
21 Execution timed out 2074 ms 2136 KB Time limit exceeded
22 Halted 0 ms 0 KB -