Submission #230626

#	Time	Username	Problem	Language	Result	Execution time	Memory
230626		brcode	Boat (APIO16_boat)	C++14	100 / 100	682 ms	8440 KiB

boat

#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 c[2*MAXN][MAXN];
long long fac[2*MAXN];
vector<long long> pts;
long long nxt;
map<long long,long long> m1;
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); 
} 
   

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(int i=1;i<pts.size();i++){
        c[i][1] = pts[i]-pts[i-1];
        for(int j=2;j<=n;j++){
            c[i][j] = 1LL*c[i][j-1]*(pts[i]-pts[i-1] +j-1)%MOD*modInverse(j,MOD)%MOD;
        }
    }
    //cout<<c[3][2]<<endl;
    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]*c[j][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 (stderr)

boat.cpp: In function 'int main()':
boat.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<pts.size();i++){
                 ~^~~~~~~~~~~
boat.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<pts.size();i++){
                       ~^~~~~~~~~~~
boat.cpp:70:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(long long j=1;j<pts.size();j++){
                           ~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42