oj.uz

Submission #1027499

# Submission time Handle Problem Language Result Execution time Memory
1027499 2024-07-19T07:07:16 Z _8_8_ Boat (APIO16_boat) C++17
27 / 100
 2000 ms 3412 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 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;
ll dp[N][N],pref[N][N],c[N][N];
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});
        // cout << b[i-1] << ' ' << b[i]-1 << '\n';
    }
    int m = (int)o.size();
    for(int i = 0;i <= m;i++){
        pref[0][i] = 1;
    }
    for(int i = 1;i <= m;i++){
        int s = (o[i - 1][1] - o[i - 1][0]+1);
        c[i][1] = s;
        for(int j = 2;j <= n;j++){
            for(int k = 0;k <= j-2;k++){
                c[i][j] = (c[i][j] + ceis(j-2,k)*ceis(s,j-k)%MOD)%MOD;
                // if(i == 1 && j == 3){
                //     cout << k << ' ' << ceis(j,k)*ceis(s,j-k)%MOD << '\n';
                // }
            }
        }
    }
    // return;
    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]*c[j][col]%MOD;
                        // cout << j << ' ' << col << ' ' << c[j][col]%MOD << "x\n";
                        if(dp[j][j] >= MOD) dp[i][j] -= MOD;
                    }
                }
            }
        }
        for(int j = 1;j <= m;j++){
            // cout << dp[i][j] << ' ';
            pref[i][j] = (pref[i][j - 1] + dp[i][j])%MOD;
        }
        // cout << '\n';    
    }
    cout << (pref[n][m]-1+MOD)%MOD << '\n';
}
int 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 Execution timed out 2063 ms 2532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 2532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 3156 KB Output is correct
2 Correct 524 ms 3156 KB Output is correct
3 Correct 520 ms 3412 KB Output is correct
4 Correct 523 ms 3156 KB Output is correct
5 Correct 525 ms 3156 KB Output is correct
6 Correct 513 ms 3160 KB Output is correct
7 Correct 527 ms 3156 KB Output is correct
8 Correct 526 ms 3296 KB Output is correct
9 Correct 531 ms 3156 KB Output is correct
10 Correct 526 ms 3188 KB Output is correct
11 Correct 523 ms 3412 KB Output is correct
12 Correct 523 ms 3156 KB Output is correct
13 Correct 518 ms 3188 KB Output is correct
14 Correct 512 ms 3156 KB Output is correct
15 Correct 512 ms 3324 KB Output is correct
16 Correct 264 ms 3324 KB Output is correct
17 Correct 257 ms 3156 KB Output is correct
18 Correct 262 ms 3156 KB Output is correct
19 Correct 262 ms 3300 KB Output is correct
20 Correct 263 ms 3328 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 2532 KB Time limit exceeded
2 Halted 0 ms 0 KB -