oj.uz

Submission #965428

# Submission time Handle Problem Language Result Execution time Memory
965428 2024-04-18T14:01:11 Z steveonalex Boat (APIO16_boat) C++17
9 / 100
 2000 ms 4776 KB 
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const long MOD = 1e9 + 7;
ll fast_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return ans;
}
 
ll inverse(ll a){return fast_pow(a, MOD - 2);}
 
const long N = 505;
ll fact[N], ifact[N];
 
void prepare(){
    fact[0] = 1;
    for(long i = 1; i<N; ++i) fact[i] = fact[i-1] * i % MOD;
    ifact[N-1]= inverse(fact[N-1]);
    for(long i = N-1; i>=1; --i) ifact[i-1] = ifact[i] * i % MOD;
}
 
ll C(long n, long k){
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}
 
ll eulerCandy(long s, long k){
    return C(s + k - 1, k - 1);
}
 
ll normie(ll a){
    a %= MOD;
    if (a < 0) a += MOD;
    return a;
}

void add(int &a, int b){
    a += b;
    if (a >= MOD) a -= MOD;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += MOD;
}

int dp[N * 2][N], s[N * 2][N];

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

    prepare();

    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for(int i= 0; i<n; ++i) cin >> a[i].first >> a[i].second;

    vector<int> b;
    for(pair<int, int> i: a){
        b.push_back(i.first - 1);
        b.push_back(i.second);
    }
    remove_dup(b);

    vector<pair<int, int>> range;
    range.push_back({0, 0});
    for(int i= 1; i<(int)b.size(); ++i) range.push_back({b[i-1] + 1, b[i]});

    a.insert(a.begin(), {0, 0});

    dp[0][0] = 1;
    for(int i= 0; i <= n; ++i) s[0][i] = 1;
    for(int i= 0; i<range.size(); ++i) s[i][0] = 1;

    for(int layer = 1; layer < (int)range.size(); ++layer){
        int len = range[layer].second - range[layer].first + 1;
        vector<int> fuck(min(n, len) + 1, 1); 
        for(int i = 1; i<(int)fuck.size(); ++i)
            fuck[i] = 1LL * fuck[i-1] * (len - i + 1) % MOD;
        for(int i = 1; i<(int)fuck.size(); ++i) 
            fuck[i] = 1LL * fuck[i] * ifact[i] % MOD;

        vector<int> love(n+1);
        love[1] = len;
        for(int i = 2; i<=n; ++i){
            for(int t = 2; t <= min(fuck.size() - 1, i); ++t){
                add(love[i], 1LL * fuck[t] * C(i - 2, t - 2) % MOD);
            }
        }

        for(int i = 1; i<=n; ++i){
            if (a[i].first > range[layer].first || range[layer].second > a[i].second) continue;
            int sum = 0;
            for(int x = 0; x < layer; ++x) for(int y = 0; y < i; ++y) add(sum, dp[x][y]);
            int cnt = 0;
            for(int j = i; j<=n; ++j){
                if (a[j].first > range[layer].first || range[layer].second > a[j].second) continue;
                cnt++;
                dp[layer][j] = 1LL * sum * love[cnt] % MOD;
            }
        }
        for(int i = 1; i<=n; ++i){
            s[layer][i] = dp[layer][i];
            add(s[layer][i], s[layer-1][i]);
            add(s[layer][i], s[layer][i-1]);
            sub(s[layer][i], s[layer-1][i-1]);
        }
    }

    int ans = 0;
    for(int j = 1; j< range.size(); ++j) 
    for(int i = 1; i<=n; ++i) add(ans, dp[j][i]);
 
    cout << ans << "\n";
    

    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i= 0; i<range.size(); ++i) s[i][0] = 1;
      |                   ~^~~~~~~~~~~~~
boat.cpp:158:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int j = 1; j< range.size(); ++j)
      |                    ~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 4776 KB Output is correct
2 Correct 447 ms 4048 KB Output is correct
3 Correct 447 ms 4180 KB Output is correct
4 Correct 451 ms 4260 KB Output is correct
5 Correct 450 ms 4256 KB Output is correct
6 Correct 472 ms 4436 KB Output is correct
7 Correct 496 ms 4280 KB Output is correct
8 Correct 485 ms 4192 KB Output is correct
9 Correct 473 ms 4332 KB Output is correct
10 Correct 477 ms 4368 KB Output is correct
11 Correct 473 ms 4696 KB Output is correct
12 Correct 471 ms 4276 KB Output is correct
13 Correct 488 ms 4264 KB Output is correct
14 Correct 470 ms 4436 KB Output is correct
15 Correct 474 ms 4224 KB Output is correct
16 Correct 75 ms 2904 KB Output is correct
17 Correct 81 ms 2648 KB Output is correct
18 Correct 78 ms 2900 KB Output is correct
19 Correct 80 ms 2652 KB Output is correct
20 Correct 80 ms 2648 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 4776 KB Output is correct
2 Correct 447 ms 4048 KB Output is correct
3 Correct 447 ms 4180 KB Output is correct
4 Correct 451 ms 4260 KB Output is correct
5 Correct 450 ms 4256 KB Output is correct
6 Correct 472 ms 4436 KB Output is correct
7 Correct 496 ms 4280 KB Output is correct
8 Correct 485 ms 4192 KB Output is correct
9 Correct 473 ms 4332 KB Output is correct
10 Correct 477 ms 4368 KB Output is correct
11 Correct 473 ms 4696 KB Output is correct
12 Correct 471 ms 4276 KB Output is correct
13 Correct 488 ms 4264 KB Output is correct
14 Correct 470 ms 4436 KB Output is correct
15 Correct 474 ms 4224 KB Output is correct
16 Correct 75 ms 2904 KB Output is correct
17 Correct 81 ms 2648 KB Output is correct
18 Correct 78 ms 2900 KB Output is correct
19 Correct 80 ms 2652 KB Output is correct
20 Correct 80 ms 2648 KB Output is correct
21 Execution timed out 2065 ms 2960 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 4776 KB Output is correct
2 Correct 447 ms 4048 KB Output is correct
3 Correct 447 ms 4180 KB Output is correct
4 Correct 451 ms 4260 KB Output is correct
5 Correct 450 ms 4256 KB Output is correct
6 Correct 472 ms 4436 KB Output is correct
7 Correct 496 ms 4280 KB Output is correct
8 Correct 485 ms 4192 KB Output is correct
9 Correct 473 ms 4332 KB Output is correct
10 Correct 477 ms 4368 KB Output is correct
11 Correct 473 ms 4696 KB Output is correct
12 Correct 471 ms 4276 KB Output is correct
13 Correct 488 ms 4264 KB Output is correct
14 Correct 470 ms 4436 KB Output is correct
15 Correct 474 ms 4224 KB Output is correct
16 Correct 75 ms 2904 KB Output is correct
17 Correct 81 ms 2648 KB Output is correct
18 Correct 78 ms 2900 KB Output is correct
19 Correct 80 ms 2652 KB Output is correct
20 Correct 80 ms 2648 KB Output is correct
21 Execution timed out 2065 ms 2960 KB Time limit exceeded
22 Halted 0 ms 0 KB -