Submission #1224439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224439		dosts	Boat (APIO16_boat)	C++20	100 / 100	347 ms	8308 KiB

boat

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 2e6+1, inf = 2e9;

int add(int x,int y) {
    if ((x + y) >= MOD) return x + y - MOD;
    return x + y;
}

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x, y >> 1);
    e = mult(e, e);
    if (y & 1) e = mult(e, x);
    return e;
}
int divide(int x, int y) {
    return mult(x, expo(y, MOD - 2));
}


void solve() {
    int n;
    cin >> n;
    vi a(n+1),b(n+1);
    vi v;
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];
    for (int i=1;i<=n;i++) v.push_back(a[i]-1);
    for (int i=1;i<=n;i++) v.push_back(b[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int sz = big(v);
    int cho[sz+1][n+1]{};
    for (int i=2;i<=sz;i++) {
        cho[i][1] = v[i-1]-v[i-2];
        for (int j=2;j<=n;j++) {
            cho[i][j] = cho[i][j-1];
            cho[i][j] = mult(cho[i][j],v[i-1]-v[i-2]+j-1);
            cho[i][j] = mult(cho[i][j],divide(1,j));
        }
    }
    int dp[n+1][sz+1]{};
    for (int i=0;i<=sz;i++) dp[0][i] = 1;
    for (int i=1;i<=n;i++) {
        dp[i][0] = 1;
        for (int j=1;j<=sz;j++) {
            dp[i][j] = dp[i][j-1];
            int nm = 0;
            for (int k = i;k>=1;k--) {
                if (a[k] <= v[j-1] && b[k] >= v[j-1]) {
                    nm++;
                    dp[i][j] = add(dp[i][j],mult(cho[j][nm],dp[k-1][j-1]));
                }
            }
        }
    }
    cout << add(dp[n][sz],MOD-1) << '\n';
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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