oj.uz

Submission #230611

# Submission time Handle Problem Language Result Execution time Memory
230611 2020-05-10T14:54:39 Z brcode Boat (APIO16_boat) C++14
9 / 100
 542 ms 6648 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MAXN = 510;
long long a[MAXN];
long long b[MAXN];
long long dp[MAXN][2*MAXN];
long long comb[2*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;
   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<=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: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 302 ms 4344 KB Output is correct
2 Correct 299 ms 4508 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 299 ms 4472 KB Output is correct
5 Correct 295 ms 4344 KB Output is correct
6 Correct 210 ms 4344 KB Output is correct
7 Correct 218 ms 4356 KB Output is correct
8 Correct 202 ms 4472 KB Output is correct
9 Correct 219 ms 4344 KB Output is correct
10 Correct 207 ms 4344 KB Output is correct
11 Correct 201 ms 4472 KB Output is correct
12 Correct 212 ms 4364 KB Output is correct
13 Correct 204 ms 4344 KB Output is correct
14 Correct 191 ms 4344 KB Output is correct
15 Correct 208 ms 4472 KB Output is correct
16 Correct 66 ms 3064 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 71 ms 3192 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 4344 KB Output is correct
2 Correct 299 ms 4508 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 299 ms 4472 KB Output is correct
5 Correct 295 ms 4344 KB Output is correct
6 Correct 210 ms 4344 KB Output is correct
7 Correct 218 ms 4356 KB Output is correct
8 Correct 202 ms 4472 KB Output is correct
9 Correct 219 ms 4344 KB Output is correct
10 Correct 207 ms 4344 KB Output is correct
11 Correct 201 ms 4472 KB Output is correct
12 Correct 212 ms 4364 KB Output is correct
13 Correct 204 ms 4344 KB Output is correct
14 Correct 191 ms 4344 KB Output is correct
15 Correct 208 ms 4472 KB Output is correct
16 Correct 66 ms 3064 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 71 ms 3192 KB Output is correct
21 Correct 379 ms 5624 KB Output is correct
22 Correct 385 ms 5624 KB Output is correct
23 Correct 393 ms 5504 KB Output is correct
24 Correct 414 ms 5496 KB Output is correct
25 Correct 419 ms 5496 KB Output is correct
26 Correct 495 ms 6520 KB Output is correct
27 Correct 542 ms 6604 KB Output is correct
28 Correct 504 ms 6648 KB Output is correct
29 Correct 522 ms 6392 KB Output is correct
30 Runtime error 8 ms 1280 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 302 ms 4344 KB Output is correct
2 Correct 299 ms 4508 KB Output is correct
3 Correct 297 ms 4344 KB Output is correct
4 Correct 299 ms 4472 KB Output is correct
5 Correct 295 ms 4344 KB Output is correct
6 Correct 210 ms 4344 KB Output is correct
7 Correct 218 ms 4356 KB Output is correct
8 Correct 202 ms 4472 KB Output is correct
9 Correct 219 ms 4344 KB Output is correct
10 Correct 207 ms 4344 KB Output is correct
11 Correct 201 ms 4472 KB Output is correct
12 Correct 212 ms 4364 KB Output is correct
13 Correct 204 ms 4344 KB Output is correct
14 Correct 191 ms 4344 KB Output is correct
15 Correct 208 ms 4472 KB Output is correct
16 Correct 66 ms 3064 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 71 ms 3192 KB Output is correct
21 Correct 379 ms 5624 KB Output is correct
22 Correct 385 ms 5624 KB Output is correct
23 Correct 393 ms 5504 KB Output is correct
24 Correct 414 ms 5496 KB Output is correct
25 Correct 419 ms 5496 KB Output is correct
26 Correct 495 ms 6520 KB Output is correct
27 Correct 542 ms 6604 KB Output is correct
28 Correct 504 ms 6648 KB Output is correct
29 Correct 522 ms 6392 KB Output is correct
30 Runtime error 8 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -