oj.uz

Submission #230614

# Submission time Handle Problem Language Result Execution time Memory
230614 2020-05-10T15:03:23 Z brcode Boat (APIO16_boat) C++14
9 / 100
 511 ms 6520 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MAXN = 501;
long long a[MAXN];
long long b[MAXN];
long long dp[MAXN][2*MAXN];
long long comb[2*MAXN][MAXN];
long long fac[2*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;
   if(r==1){
       return n;
   }
   
  
    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<=1001;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:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:76: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 301 ms 4472 KB Output is correct
2 Correct 301 ms 4344 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 297 ms 4332 KB Output is correct
5 Correct 296 ms 4460 KB Output is correct
6 Correct 196 ms 4344 KB Output is correct
7 Correct 190 ms 4344 KB Output is correct
8 Correct 201 ms 4344 KB Output is correct
9 Correct 213 ms 4472 KB Output is correct
10 Correct 208 ms 4348 KB Output is correct
11 Correct 191 ms 4344 KB Output is correct
12 Correct 204 ms 4344 KB Output is correct
13 Correct 197 ms 4384 KB Output is correct
14 Correct 185 ms 4344 KB Output is correct
15 Correct 194 ms 4344 KB Output is correct
16 Correct 66 ms 3192 KB Output is correct
17 Correct 72 ms 3192 KB Output is correct
18 Correct 68 ms 3192 KB Output is correct
19 Correct 68 ms 3192 KB Output is correct
20 Correct 69 ms 3192 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 4472 KB Output is correct
2 Correct 301 ms 4344 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 297 ms 4332 KB Output is correct
5 Correct 296 ms 4460 KB Output is correct
6 Correct 196 ms 4344 KB Output is correct
7 Correct 190 ms 4344 KB Output is correct
8 Correct 201 ms 4344 KB Output is correct
9 Correct 213 ms 4472 KB Output is correct
10 Correct 208 ms 4348 KB Output is correct
11 Correct 191 ms 4344 KB Output is correct
12 Correct 204 ms 4344 KB Output is correct
13 Correct 197 ms 4384 KB Output is correct
14 Correct 185 ms 4344 KB Output is correct
15 Correct 194 ms 4344 KB Output is correct
16 Correct 66 ms 3192 KB Output is correct
17 Correct 72 ms 3192 KB Output is correct
18 Correct 68 ms 3192 KB Output is correct
19 Correct 68 ms 3192 KB Output is correct
20 Correct 69 ms 3192 KB Output is correct
21 Correct 398 ms 5488 KB Output is correct
22 Correct 404 ms 5496 KB Output is correct
23 Correct 386 ms 5244 KB Output is correct
24 Correct 390 ms 5624 KB Output is correct
25 Correct 404 ms 5368 KB Output is correct
26 Correct 499 ms 6520 KB Output is correct
27 Correct 511 ms 6392 KB Output is correct
28 Correct 492 ms 6264 KB Output is correct
29 Correct 498 ms 6300 KB Output is correct
30 Runtime error 7 ms 1152 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 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 301 ms 4472 KB Output is correct
2 Correct 301 ms 4344 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 297 ms 4332 KB Output is correct
5 Correct 296 ms 4460 KB Output is correct
6 Correct 196 ms 4344 KB Output is correct
7 Correct 190 ms 4344 KB Output is correct
8 Correct 201 ms 4344 KB Output is correct
9 Correct 213 ms 4472 KB Output is correct
10 Correct 208 ms 4348 KB Output is correct
11 Correct 191 ms 4344 KB Output is correct
12 Correct 204 ms 4344 KB Output is correct
13 Correct 197 ms 4384 KB Output is correct
14 Correct 185 ms 4344 KB Output is correct
15 Correct 194 ms 4344 KB Output is correct
16 Correct 66 ms 3192 KB Output is correct
17 Correct 72 ms 3192 KB Output is correct
18 Correct 68 ms 3192 KB Output is correct
19 Correct 68 ms 3192 KB Output is correct
20 Correct 69 ms 3192 KB Output is correct
21 Correct 398 ms 5488 KB Output is correct
22 Correct 404 ms 5496 KB Output is correct
23 Correct 386 ms 5244 KB Output is correct
24 Correct 390 ms 5624 KB Output is correct
25 Correct 404 ms 5368 KB Output is correct
26 Correct 499 ms 6520 KB Output is correct
27 Correct 511 ms 6392 KB Output is correct
28 Correct 492 ms 6264 KB Output is correct
29 Correct 498 ms 6300 KB Output is correct
30 Runtime error 7 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -