Submission #681624

#	Time	Username	Problem	Language	Result	Execution time	Memory
681624		79brue	Boat (APIO16_boat)	C++17	100 / 100	908 ms	19972 KiB

boat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y%2) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}

ll modInv(ll x){
    return mpow(x, MOD-2);
}

int n, k;
ll a[502], b[502];
ll arr[1002];

void input();
void init();
void solve();
void output();

int main(){
    input();
    init();
    solve();
    output();
}

void input(){
    vector<int> vec;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
        a[i]--;
        vec.push_back(a[i]);
        vec.push_back(b[i]);
    }
    vec.push_back(0);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    k = (int)vec.size() - 1;
    for(int i=0; i<=k; i++) arr[i] = vec[i];

    for(int i=1; i<=n; i++){
        a[i] = lower_bound(arr, arr+k+1, a[i]) - arr + 1;
        b[i] = lower_bound(arr, arr+k+1, b[i]) - arr;
    }
}

ll nCk[502][502];
ll xCi[1002][502];
ll xySum[1002][502];

void init(){
    /// nCk
    for(int i=0; i<=n; i++){
        nCk[i][0] = nCk[i][i] = 1;
        for(int j=1; j<i; j++){
            nCk[i][j] = (nCk[i-1][j] + nCk[i-1][j-1]) % MOD;
        }
    }

    /// xCi
    for(int i=1; i<=k; i++){
        ll X = arr[i] - arr[i-1];
        xCi[i][1] = X;
        for(int j=2; j<=n; j++){
            xCi[i][j] = xCi[i][j-1] * (X-j+1) % MOD * modInv(j) % MOD;
        }
    }

    /// xyMult
    for(int i=1; i<=k; i++){
        for(int j=1; j<=n; j++){
            for(int d=1; d<=j; d++){
                xySum[i][j] = (xySum[i][j] + xCi[i][d] * nCk[j-1][d-1]) % MOD;
            }
        }
    }
}

int sum[502][1002];
ll DP[502][1002];
ll DPsum[502][1002];

void solve(){
    /// sum
    for(int i=1; i<=n; i++){
        for(int j=a[i]; j<=b[i]; j++){
            sum[i][j] = 1;
        }
    }
    for(int j=1; j<=k; j++) for(int i=1; i<=n; i++) sum[i][j] += sum[i-1][j];

    DP[0][0] = 1;
    for(int i=0; i<=k; i++) DPsum[0][i] = 1;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(j < a[i] || b[i] < j) continue;
            for(int prv=0; prv<i; prv++){
                DP[i][j] = (DP[i][j] + DPsum[prv][j-1] * xySum[j][sum[i][j]-sum[prv][j]]) % MOD;
            }
        }

        for(int j=1; j<=k; j++) DPsum[i][j] = (DPsum[i][j-1] + DP[i][j]) % MOD;

//        for(int j=1; j<=k; j++) printf("%lld ", DP[i][j]);
//        puts("");
    }
}

ll ans;

void output(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            ans = (ans + DP[i][j]) % MOD;
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

boat.cpp: In function 'void input()':
boat.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%lld %lld", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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