oj.uz

답안 #230604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230604 2020-05-10T14:45:22 Z brcode Boat (APIO16_boat) C++14
9 / 100
 2000 ms 4416 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() {
    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:63:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:69: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

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 4344 KB Output is correct
2 Correct 299 ms 4344 KB Output is correct
3 Correct 297 ms 4300 KB Output is correct
4 Correct 292 ms 4372 KB Output is correct
5 Correct 293 ms 4344 KB Output is correct
6 Correct 204 ms 4344 KB Output is correct
7 Correct 195 ms 4344 KB Output is correct
8 Correct 199 ms 4344 KB Output is correct
9 Correct 210 ms 4344 KB Output is correct
10 Correct 216 ms 4348 KB Output is correct
11 Correct 202 ms 4344 KB Output is correct
12 Correct 210 ms 4344 KB Output is correct
13 Correct 202 ms 4344 KB Output is correct
14 Correct 187 ms 4344 KB Output is correct
15 Correct 203 ms 4416 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 101 ms 3064 KB Output is correct
18 Correct 101 ms 3064 KB Output is correct
19 Correct 105 ms 3192 KB Output is correct
20 Correct 103 ms 3068 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 4344 KB Output is correct
2 Correct 299 ms 4344 KB Output is correct
3 Correct 297 ms 4300 KB Output is correct
4 Correct 292 ms 4372 KB Output is correct
5 Correct 293 ms 4344 KB Output is correct
6 Correct 204 ms 4344 KB Output is correct
7 Correct 195 ms 4344 KB Output is correct
8 Correct 199 ms 4344 KB Output is correct
9 Correct 210 ms 4344 KB Output is correct
10 Correct 216 ms 4348 KB Output is correct
11 Correct 202 ms 4344 KB Output is correct
12 Correct 210 ms 4344 KB Output is correct
13 Correct 202 ms 4344 KB Output is correct
14 Correct 187 ms 4344 KB Output is correct
15 Correct 203 ms 4416 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 101 ms 3064 KB Output is correct
18 Correct 101 ms 3064 KB Output is correct
19 Correct 105 ms 3192 KB Output is correct
20 Correct 103 ms 3068 KB Output is correct
21 Execution timed out 2077 ms 2248 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 4344 KB Output is correct
2 Correct 299 ms 4344 KB Output is correct
3 Correct 297 ms 4300 KB Output is correct
4 Correct 292 ms 4372 KB Output is correct
5 Correct 293 ms 4344 KB Output is correct
6 Correct 204 ms 4344 KB Output is correct
7 Correct 195 ms 4344 KB Output is correct
8 Correct 199 ms 4344 KB Output is correct
9 Correct 210 ms 4344 KB Output is correct
10 Correct 216 ms 4348 KB Output is correct
11 Correct 202 ms 4344 KB Output is correct
12 Correct 210 ms 4344 KB Output is correct
13 Correct 202 ms 4344 KB Output is correct
14 Correct 187 ms 4344 KB Output is correct
15 Correct 203 ms 4416 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 101 ms 3064 KB Output is correct
18 Correct 101 ms 3064 KB Output is correct
19 Correct 105 ms 3192 KB Output is correct
20 Correct 103 ms 3068 KB Output is correct
21 Execution timed out 2077 ms 2248 KB Time limit exceeded
22 Halted 0 ms 0 KB -