Submission #43714

#	Time	Username	Problem	Language	Result	Execution time	Memory
43714		spencercompton	Boat (APIO16_boat)	C++11	100 / 100	1605 ms	1040 KiB

boat

#include<bits/stdc++.h>
using namespace std;
long long mod = 1000000007LL;
long long perm[501];
long long fastpow(long long base, int ex){
    if(ex==0){
        return 1LL;
    }
    if(ex%2==1){
        return (base * fastpow(base,ex-1))%mod;
    }
    else{
        return fastpow((base*base)%mod,ex/2);
    }
}
long long modinv(long long x){
    return fastpow(x,(int)mod-2);
}
long long choose(long long n, long long k){
    if(k<0LL || k>n){
        return 0LL;
    }
    long long ret = 1LL;
    for(long long i = 0; i<k; i++){
        ret *= (n-i);
        ret %= mod;
    }
    ret *= perm[k];
    ret %= mod;
    return ret;
}
int main(){
    int n;
    cin >> n;
    int a[n+1];
    int b[n+1];
    a[0] = -10;
    b[0] = -10;
    perm[0] = 1LL;
    for(int i = 1; i<=500; i++){
        perm[i] = perm[i-1] * (long long)i;
        perm[i] %= mod;
    }
    for(int i = 0; i<=500; i++){
        perm[i] = modinv(perm[i]);
    }
    for(int i = 1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    vector<int> all;
    for(int i = 1; i<=n; i++){
        all.push_back(b[i]);
        all.push_back(a[i]-1);
    }
    sort(all.begin(),all.end());
    vector<int> extralist;
    extralist.push_back(all[0]);
    for(int i = 1; i<all.size(); i++){
        if(all[i]!=all[i-1]){
            extralist.push_back(all[i]);
        }
    }
    all = extralist;
    extralist.clear();
    long long dp[n+1];
    dp[0] = 1LL;
    for(int i = 1; i<=n; i++){
        dp[i] = 0LL;
    }
    for(int i = 1; i<all.size(); i++){
        int curVal = all[i];
        long long k = all[i]-all[i-1];
        vector<long long> inds;
        vector<long long> li;
        vector<long long> li2;
        long long sum = 0LL;
        for(int j = 0; j<=n; j++){
            if(a[j]<=curVal && curVal<=b[j]){
                inds.push_back(j);
                li.push_back(dp[j]);
                li2.push_back(sum);
            }
            else{
                sum += dp[j];
                sum %= mod;
            }
        }
        for(int j = 0; j<li2.size(); j++){
            li.push_back(li2[j]);
        }
        int sz = inds.size();
        long long next[sz];
        for(int j = 0; j<sz; j++){
            next[j] = 0LL;
        }
        long long cn = sz+k-2LL;
        long long ck = sz;
        long long cur = -1LL;
        if(ck>=0 && ck<=cn){
            cur = choose(cn,ck);
        }
        for(int h = 0; h<sz; h++){
            next[sz-1-h] += k*li2[sz-1-h];
            next[sz-1-h] %= mod;
        }
        for(int j = 0; j+1<sz; j++){
            if(ck<0 || ck>cn){
                break;
            }
            for(int h = 0; h<=j; h++){
                next[sz-1-h] += li2[j-h]*cur;
                next[sz-1-h] %= mod;
            }
            if(j+1<sz){
                cn--;
                ck--;
                if(ck<0){
                    break;
                }
                cur *= modinv(cn+1LL);
                cur %= mod;
                cur *= ck+1LL;
                cur %= mod;
            }
        }
        
        
        cn = sz+k-2LL;
        ck = sz-1LL;
        cur = -1LL;
        if(ck>=0 && ck<=cn){
            cur = choose(cn,ck);
        }
        for(int h = 0; h<sz; h++){
            next[sz-1-h] += li[sz-1-h];
            next[sz-1-h] %= mod;
        }
        for(int j = 0; j+1<sz; j++){
            if(ck<0 || ck>cn){
                break;
            }
            for(int h = 0; h<=j; h++){
                next[sz-1-h] += li[j-h]*cur;
                next[sz-1-h] %= mod;
            }
            if(j+1<sz){
                cn--;
                ck--;
                if(ck<0){
                    break;
                }
                cur *= modinv(cn+1LL);
                cur %= mod;
                cur *= ck+1LL;
                cur %= mod;
            }
        }
        
        
        for(int i = 0; i<sz; i++){
            dp[inds[i]] = next[i]%mod;
        }
        
        //expo stuff
    }
    long long ans = 0LL;
    for(int i = 1; i<=n; i++){
        ans += dp[i];
        ans %= mod;
    }
    cout << ans << endl;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i<all.size(); i++){
                     ^
boat.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i<all.size(); i++){
                     ^
boat.cpp:88:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j<li2.size(); j++){
                         ^

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