oj.uz

Submission #1027541

# Submission time Handle Problem Language Result Execution time Memory
1027541 2024-07-19T07:25:12 Z _8_8_ Boat (APIO16_boat) C++17
0 / 100
 985 ms 9556 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 1e3 + 20, MOD = (int)1e9+7;

ll binpow(ll a,ll b) {
    ll ans = 1,k = a;
    while(b) {
        if(b % 2)ans *= k;
        ans %= MOD;
        k *= k;
        k %= MOD;
        b /= 2ll;
    }
    return ans;
}
ll bp[N];
ll ceis(ll n,ll k){
    if(k > n) return 0;     
    ll d = 1;
    for(ll i = n - k + 1;i <= n;i++){
        d = i % MOD * d % MOD;
    }
    for(ll i = 2;i <= k;i++){   
        d = d * bp[i]%MOD;
    }
    return d;
}
int n;
array<int,2> a[N];
vector<int> b;
vector<array<int,2>> o;
int dp[N][N],pref[N][N],c[N][N],prec[N/2][N/2];
int m;
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i][0] >> a[i][1];
        b.push_back(a[i][0]);
        b.push_back(a[i][1] + 1);
        bp[i] = binpow(i,MOD-2);
    }
    sort(b.begin(),b.end());
    b.resize(unique(b.begin(),b.end()) - b.begin()); 
    for(int i = 1;i < (int)b.size();i++){
        o.push_back({b[i-1],b[i]-1});
    }
    int m = (int)o.size();
    for(int i = 0;i <= m;i++){
        pref[0][i] = 1;
    }
    for(int i = 0;i <= n;i++){
        for(int j = 0;j <= i;j++){
            prec[i][j] = ceis(i,j);
        }
    }
    for(int i = 1;i <= m;i++){
        int s = (o[i - 1][1] - o[i - 1][0]+1);
        c[i][1] = s;
        vector<int> C(n+1,0);
        for(int j = 0;j <= n;++j){
            C[j] = ceis(s,j);
        }
        for(int j = 2;j <= n;j++){
            for(int k = 0;k <= j-2;k++){
                c[i][j] = (c[i][j] + prec[j-2][k]*1ll*C[j-k]%MOD);
                if(c[i][j] >= MOD) c[i][j] -= MOD;
            }
        }
    }
    for(int i = 1;i <= n;i++){
        pref[i][0] = 1;
        for(int j = 1;j <= m;j++){
            dp[i][j] = dp[i - 1][j];
            if(a[i][0] <= o[j - 1][0] && a[i][1] >= o[j-1][1]){
                for(int k = i,col = 0;k >= 1;k--){
                    if(a[k][0] <= o[j-1][0] && a[k][1] >= o[j-1][1]){
                        ++col;
                        dp[i][j] += pref[k-1][j-1]*1ll*c[j][col]%MOD;
                        if(dp[j][j] >= MOD) dp[i][j] -= MOD;
                    }
                }
            }
        }
        for(int j = 1;j <= m;j++){
            pref[i][j] = (pref[i][j - 1] + dp[i][j])%MOD;
        }
    }
    cout << (pref[n][m]-1+MOD)%MOD << '\n';
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 9432 KB Output is correct
2 Correct 944 ms 9448 KB Output is correct
3 Correct 978 ms 9424 KB Output is correct
4 Correct 921 ms 9280 KB Output is correct
5 Correct 885 ms 9360 KB Output is correct
6 Correct 985 ms 9264 KB Output is correct
7 Correct 894 ms 9468 KB Output is correct
8 Correct 886 ms 9300 KB Output is correct
9 Correct 868 ms 9512 KB Output is correct
10 Correct 874 ms 9296 KB Output is correct
11 Correct 886 ms 9552 KB Output is correct
12 Correct 899 ms 9556 KB Output is correct
13 Correct 893 ms 9488 KB Output is correct
14 Correct 958 ms 9480 KB Output is correct
15 Correct 921 ms 9356 KB Output is correct
16 Incorrect 319 ms 9376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 9432 KB Output is correct
2 Correct 944 ms 9448 KB Output is correct
3 Correct 978 ms 9424 KB Output is correct
4 Correct 921 ms 9280 KB Output is correct
5 Correct 885 ms 9360 KB Output is correct
6 Correct 985 ms 9264 KB Output is correct
7 Correct 894 ms 9468 KB Output is correct
8 Correct 886 ms 9300 KB Output is correct
9 Correct 868 ms 9512 KB Output is correct
10 Correct 874 ms 9296 KB Output is correct
11 Correct 886 ms 9552 KB Output is correct
12 Correct 899 ms 9556 KB Output is correct
13 Correct 893 ms 9488 KB Output is correct
14 Correct 958 ms 9480 KB Output is correct
15 Correct 921 ms 9356 KB Output is correct
16 Incorrect 319 ms 9376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 9432 KB Output is correct
2 Correct 944 ms 9448 KB Output is correct
3 Correct 978 ms 9424 KB Output is correct
4 Correct 921 ms 9280 KB Output is correct
5 Correct 885 ms 9360 KB Output is correct
6 Correct 985 ms 9264 KB Output is correct
7 Correct 894 ms 9468 KB Output is correct
8 Correct 886 ms 9300 KB Output is correct
9 Correct 868 ms 9512 KB Output is correct
10 Correct 874 ms 9296 KB Output is correct
11 Correct 886 ms 9552 KB Output is correct
12 Correct 899 ms 9556 KB Output is correct
13 Correct 893 ms 9488 KB Output is correct
14 Correct 958 ms 9480 KB Output is correct
15 Correct 921 ms 9356 KB Output is correct
16 Incorrect 319 ms 9376 KB Output isn't correct
17 Halted 0 ms 0 KB -