Submission #598908

#	Time	Username	Problem	Language	Result	Execution time	Memory
598908		radal	Boat (APIO16_boat)	C++17	100 / 100	1723 ms	4400 KiB

boat

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 5e2+20,mod = 1e9+7 ,inf = 1e9+10,maxm = (1 << 10)+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z;
}
int dp[2][2*N][N],sum[2][2*N];
int a[N],b[N],n,inv[N*2];
int main(){
    vector<int> ve;
    cin >> n;
    ve.reserve(2*n);
    rep(i,1,n+1){
        cin >> a[i] >> b[i];
        b[i]++;
        ve.pb(a[i]);
        ve.pb(b[i]);
    }
    sort(all(ve));
    rep(i,1,n+1){
        a[i] = lower_bound(all(ve),a[i])-ve.begin();
        b[i] = lower_bound(all(ve),b[i])-ve.begin();
    }
    int nn = 2*n+1;
    rep(i,0,n+2) inv[i] = poww(i,mod-2);
    rep(i,1,n+1){
        bool f = (i&1);
        rep(j,0,nn){
            sum[f][j] = 0;
            rep(k,1,n+1){
                if (k > i) break;
                dp[f][j][k] = dp[1-f][j][k];
                if (j < a[i] || j >= b[i]){
                    sum[f][j] = (sum[f][j]+dp[f][j][k])%mod;
                    continue;
                }
                if (k > 1){
                    dp[f][j][k] = (dp[f][j][k]+1ll*dp[1-f][j][k-1]*inv[k]%mod*(ve[j+1]-ve[j]-k+1)%mod)%mod;
                }
                else{
                    dp[f][j][k] = (dp[f][j][k]+ve[j+1]-ve[j])%mod;
                    rep(g,0,j){
                        dp[f][j][k] = (dp[f][j][k]+1ll*(ve[j+1]-ve[j])*sum[1-f][g]%mod)%mod;
                    }
                }
                sum[f][j] = (sum[f][j]+dp[f][j][k])%mod;
            }
        }
    }
    bool f = n%2;
    int ans = 0;
    rep(i,0,nn){
        ans = (ans+sum[f][i])%mod;
    }
    cout << ans;
}

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