Submission #230102

#	Time	Username	Problem	Language	Result	Execution time	Memory
230102		lyc	Boat (APIO16_boat)	C++14	9 / 100	1549 ms	7676 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 505;
const int MOD = 1e9+7;

int N, A[MX_N], B[MX_N];
vector<int> val;

int dp[MX_N][2*MX_N];
int pre[MX_N][2*MX_N];

int inv[MX_N];
map<int,vector<int>> nck;
map<int,vector<int>> prod;

void precomp(int n) {
    if (nck.count(n)) return;
    auto& v = nck[n];
    v.assign(N+1,1);
    FOR(k,1,N) v[k] = 1LL * v[k-1] * (n-k+1) % MOD * inv[k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> A[i] >> B[i];
        B[i] += 1;
        val.push_back(A[i]);
        val.push_back(B[i]);
    }
    sort(ALL(val));
    val.resize(unique(ALL(val))-val.begin());
    FOR(i,1,N){
        A[i] = lower_bound(ALL(val),A[i])-val.begin();
        B[i] = lower_bound(ALL(val),B[i])-val.begin();
    }

    inv[1] = 1;
    FOR(i,2,N) inv[i] = (MOD - 1LL * (MOD/i) * inv[MOD%i] % MOD) % MOD;
    FOR(i,0,N) precomp(i);
    FOR(i,1,SZ(val)-1) precomp(val[i]-val[i-1]);
    FOR(i,1,SZ(val)-1){
        precomp(val[i]-val[i-1]);
        auto& u = nck[val[i]-val[i-1]];
        auto& v = prod[val[i]-val[i-1]];
        v.assign(N+1,0);
        FOR(x,0,N-2){
            auto& w = nck[x];
            FOR(k,0,x){
                v[x] += 1LL * u[k+2] * w[k] % MOD;
                v[x] %= MOD;
            }
        }
    }

        RFOR(x,SZ(val)-1,0){
            dp[N+1][x] = 1;
            pre[N+1][x] = dp[N+1][x];
        }
    RFOR(i,N,1){
        RFOR(x,SZ(val)-1,0){
            dp[i][x] = 0;
            if (x+1 < SZ(val)) dp[i][x] = (dp[i][x] + dp[i][x+1]) % MOD;
            if (A[i] <= x && x < B[i]) {
                FOR(j,i,N){
                    if (A[i] > x || B[i] <= x) break;
                    int coeff = 0;
                    if (i == j) {
                        coeff = val[x+1]-val[x];
                    } else {
                        coeff = prod[val[x+1]-val[x]][j-i-1];
                    }
                    int sum = (pre[j+1][x+1] - pre[N+2][x+1] + MOD) % MOD;
                    dp[i][x] = (dp[i][x] + 1LL * coeff * sum % MOD) % MOD;
                }
            }
            pre[i][x] = (pre[i+1][x] + dp[i][x]) % MOD;
            //TRACE(i _ x _ dp[i][x]);
        }
    }

    int ans = 0;
    FOR(i,1,N){
        ans = (ans + dp[i][0]) % MOD;
    }
    cout << ans;
}

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