Submission #141411

#	Time	Username	Problem	Language	Result	Execution time	Memory
141411		khsoo01	Boat (APIO16_boat)	C++11	100 / 100	693 ms	11124 KiB

boat

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll n, s[505], e[505], len[1005], cmpr[1005], segc;
ll dt[505][1005], sum[505][1005], minv[1005];

vector<ll> incl[1005];

ll bigpow (ll A, ll B) {
    if(!B) return 1;
    ll ret = bigpow(A,B/2);
    ret = (ret*ret)%mod;
    if(B%2) ret = (ret*A)%mod;
    return ret;
}

int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) {
        scanf("%lld%lld",&s[i],&e[i]); e[i]++;
        cmpr[2*i-2] = s[i];
        cmpr[2*i-1] = e[i];
    }
    cmpr[2*n] = 0; segc = 2*n+1;
    sort(cmpr,cmpr+segc);
    for(ll i=1;i<=n;i++) {
        s[i] = lower_bound(cmpr,cmpr+segc,s[i])-cmpr;
        e[i] = lower_bound(cmpr,cmpr+segc,e[i])-cmpr;
    }
    for(ll i=0;i<segc;i++) {
        len[i] = cmpr[i+1]-cmpr[i];
        for(ll j=1;j<=n;j++) {
            if(s[j]<=i && i<e[j]) incl[i].push_back(j);
        }
    }
    dt[0][0] = 1;
    for(ll i=0;i<segc;i++) sum[0][i] = 1;
    for(ll i=1;i<=n;i++) minv[i] = bigpow(i,mod-2);
    for(ll i=1;i<=n;i++) {
        for(ll j=0;j<segc;j++) {
            if(s[i]>j || j>=e[i]) {
                dt[i][j] = dt[i-1][j];
                continue;
            }
            ll bnd = upper_bound(incl[j].begin(),incl[j].end(),i)-incl[j].begin()-1;
            ll cnt = 1;
            for(int k=0;k<=bnd;k++) {
                cnt = ((cnt*(len[j]+k))%mod*minv[k+1])%mod;
                dt[i][j] += cnt*sum[incl[j][bnd-k]-1][j-1];
                dt[i][j] %= mod;
            }
        }
        sum[i][0] = 1;
        for(ll j=1;j<segc;j++) {
            sum[i][j] = dt[i][j] + sum[i][j-1];
            sum[i][j] %= mod;
        }
    }
    printf("%lld\n",(sum[n][segc-1]+mod-1)%mod);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&s[i],&e[i]); e[i]++;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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