oj.uz

Submission #230608

# Submission time Handle Problem Language Result Execution time Memory
230608 2020-05-10T14:51:27 Z brcode Boat (APIO16_boat) C++14
9 / 100
 500 ms 6648 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MAXN = 1010;
long long a[MAXN];
long long b[MAXN];
long long dp[MAXN][MAXN];
long long comb[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(comb[n][r]){
        return comb[n][r];
    }
   
   if (r==0) 
      return 1;
   
   
  
    return comb[n][r] = (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<=2000;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:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:74: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 256 ms 4344 KB Output is correct
2 Correct 253 ms 4344 KB Output is correct
3 Correct 255 ms 4344 KB Output is correct
4 Correct 250 ms 4344 KB Output is correct
5 Correct 250 ms 4344 KB Output is correct
6 Correct 153 ms 4344 KB Output is correct
7 Correct 151 ms 4300 KB Output is correct
8 Correct 156 ms 4344 KB Output is correct
9 Correct 162 ms 4344 KB Output is correct
10 Correct 155 ms 4344 KB Output is correct
11 Correct 165 ms 4344 KB Output is correct
12 Correct 160 ms 4448 KB Output is correct
13 Correct 154 ms 4344 KB Output is correct
14 Correct 142 ms 4344 KB Output is correct
15 Correct 160 ms 4344 KB Output is correct
16 Correct 57 ms 3192 KB Output is correct
17 Correct 58 ms 3192 KB Output is correct
18 Correct 57 ms 3168 KB Output is correct
19 Correct 60 ms 3192 KB Output is correct
20 Correct 60 ms 3192 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 4344 KB Output is correct
2 Correct 253 ms 4344 KB Output is correct
3 Correct 255 ms 4344 KB Output is correct
4 Correct 250 ms 4344 KB Output is correct
5 Correct 250 ms 4344 KB Output is correct
6 Correct 153 ms 4344 KB Output is correct
7 Correct 151 ms 4300 KB Output is correct
8 Correct 156 ms 4344 KB Output is correct
9 Correct 162 ms 4344 KB Output is correct
10 Correct 155 ms 4344 KB Output is correct
11 Correct 165 ms 4344 KB Output is correct
12 Correct 160 ms 4448 KB Output is correct
13 Correct 154 ms 4344 KB Output is correct
14 Correct 142 ms 4344 KB Output is correct
15 Correct 160 ms 4344 KB Output is correct
16 Correct 57 ms 3192 KB Output is correct
17 Correct 58 ms 3192 KB Output is correct
18 Correct 57 ms 3168 KB Output is correct
19 Correct 60 ms 3192 KB Output is correct
20 Correct 60 ms 3192 KB Output is correct
21 Correct 372 ms 5568 KB Output is correct
22 Correct 376 ms 5752 KB Output is correct
23 Correct 355 ms 5496 KB Output is correct
24 Correct 366 ms 5500 KB Output is correct
25 Correct 385 ms 5624 KB Output is correct
26 Correct 470 ms 6520 KB Output is correct
27 Correct 500 ms 6648 KB Output is correct
28 Correct 477 ms 6648 KB Output is correct
29 Correct 481 ms 6496 KB Output is correct
30 Runtime error 8 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 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 256 ms 4344 KB Output is correct
2 Correct 253 ms 4344 KB Output is correct
3 Correct 255 ms 4344 KB Output is correct
4 Correct 250 ms 4344 KB Output is correct
5 Correct 250 ms 4344 KB Output is correct
6 Correct 153 ms 4344 KB Output is correct
7 Correct 151 ms 4300 KB Output is correct
8 Correct 156 ms 4344 KB Output is correct
9 Correct 162 ms 4344 KB Output is correct
10 Correct 155 ms 4344 KB Output is correct
11 Correct 165 ms 4344 KB Output is correct
12 Correct 160 ms 4448 KB Output is correct
13 Correct 154 ms 4344 KB Output is correct
14 Correct 142 ms 4344 KB Output is correct
15 Correct 160 ms 4344 KB Output is correct
16 Correct 57 ms 3192 KB Output is correct
17 Correct 58 ms 3192 KB Output is correct
18 Correct 57 ms 3168 KB Output is correct
19 Correct 60 ms 3192 KB Output is correct
20 Correct 60 ms 3192 KB Output is correct
21 Correct 372 ms 5568 KB Output is correct
22 Correct 376 ms 5752 KB Output is correct
23 Correct 355 ms 5496 KB Output is correct
24 Correct 366 ms 5500 KB Output is correct
25 Correct 385 ms 5624 KB Output is correct
26 Correct 470 ms 6520 KB Output is correct
27 Correct 500 ms 6648 KB Output is correct
28 Correct 477 ms 6648 KB Output is correct
29 Correct 481 ms 6496 KB Output is correct
30 Runtime error 8 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -