oj.uz

Submission #230606

# Submission time Handle Problem Language Result Execution time Memory
230606 2020-05-10T14:48:01 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;
                   
                  // 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<<'\n';
}

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 346 ms 4344 KB Output is correct
2 Correct 351 ms 4344 KB Output is correct
3 Correct 349 ms 4344 KB Output is correct
4 Correct 350 ms 4344 KB Output is correct
5 Correct 342 ms 4344 KB Output is correct
6 Correct 252 ms 4344 KB Output is correct
7 Correct 253 ms 4472 KB Output is correct
8 Correct 251 ms 4344 KB Output is correct
9 Correct 249 ms 4344 KB Output is correct
10 Correct 250 ms 4344 KB Output is correct
11 Correct 256 ms 4344 KB Output is correct
12 Correct 254 ms 4344 KB Output is correct
13 Correct 245 ms 4344 KB Output is correct
14 Correct 245 ms 4344 KB Output is correct
15 Correct 259 ms 4324 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 111 ms 3192 KB Output is correct
18 Correct 113 ms 3064 KB Output is correct
19 Correct 118 ms 3072 KB Output is correct
20 Correct 112 ms 3192 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 4344 KB Output is correct
2 Correct 351 ms 4344 KB Output is correct
3 Correct 349 ms 4344 KB Output is correct
4 Correct 350 ms 4344 KB Output is correct
5 Correct 342 ms 4344 KB Output is correct
6 Correct 252 ms 4344 KB Output is correct
7 Correct 253 ms 4472 KB Output is correct
8 Correct 251 ms 4344 KB Output is correct
9 Correct 249 ms 4344 KB Output is correct
10 Correct 250 ms 4344 KB Output is correct
11 Correct 256 ms 4344 KB Output is correct
12 Correct 254 ms 4344 KB Output is correct
13 Correct 245 ms 4344 KB Output is correct
14 Correct 245 ms 4344 KB Output is correct
15 Correct 259 ms 4324 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 111 ms 3192 KB Output is correct
18 Correct 113 ms 3064 KB Output is correct
19 Correct 118 ms 3072 KB Output is correct
20 Correct 112 ms 3192 KB Output is correct
21 Execution timed out 2084 ms 2040 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 346 ms 4344 KB Output is correct
2 Correct 351 ms 4344 KB Output is correct
3 Correct 349 ms 4344 KB Output is correct
4 Correct 350 ms 4344 KB Output is correct
5 Correct 342 ms 4344 KB Output is correct
6 Correct 252 ms 4344 KB Output is correct
7 Correct 253 ms 4472 KB Output is correct
8 Correct 251 ms 4344 KB Output is correct
9 Correct 249 ms 4344 KB Output is correct
10 Correct 250 ms 4344 KB Output is correct
11 Correct 256 ms 4344 KB Output is correct
12 Correct 254 ms 4344 KB Output is correct
13 Correct 245 ms 4344 KB Output is correct
14 Correct 245 ms 4344 KB Output is correct
15 Correct 259 ms 4324 KB Output is correct
16 Correct 111 ms 3064 KB Output is correct
17 Correct 111 ms 3192 KB Output is correct
18 Correct 113 ms 3064 KB Output is correct
19 Correct 118 ms 3072 KB Output is correct
20 Correct 112 ms 3192 KB Output is correct
21 Execution timed out 2084 ms 2040 KB Time limit exceeded
22 Halted 0 ms 0 KB -