oj.uz

Submission #965423

# Submission time Handle Problem Language Result Execution time Memory
965423 2024-04-18T13:51:18 Z steveonalex Boat (APIO16_boat) C++17
36 / 100
 2000 ms 2516 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;
}

int dp[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 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++;
                add(dp[layer][j], 1LL * sum * love[cnt] % MOD);
            }
        }
    }

    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:144: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]
  144 |     for(int j = 1; j< range.size(); ++j)
      |                    ~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 2216 KB Output is correct
2 Correct 454 ms 2128 KB Output is correct
3 Correct 449 ms 2508 KB Output is correct
4 Correct 447 ms 2384 KB Output is correct
5 Correct 451 ms 2072 KB Output is correct
6 Correct 468 ms 2388 KB Output is correct
7 Correct 474 ms 2516 KB Output is correct
8 Correct 467 ms 2380 KB Output is correct
9 Correct 482 ms 2352 KB Output is correct
10 Correct 473 ms 2392 KB Output is correct
11 Correct 468 ms 2236 KB Output is correct
12 Correct 486 ms 2380 KB Output is correct
13 Correct 482 ms 2320 KB Output is correct
14 Correct 471 ms 2240 KB Output is correct
15 Correct 482 ms 2324 KB Output is correct
16 Correct 77 ms 596 KB Output is correct
17 Correct 86 ms 948 KB Output is correct
18 Correct 77 ms 772 KB Output is correct
19 Correct 80 ms 664 KB Output is correct
20 Correct 78 ms 740 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 2216 KB Output is correct
2 Correct 454 ms 2128 KB Output is correct
3 Correct 449 ms 2508 KB Output is correct
4 Correct 447 ms 2384 KB Output is correct
5 Correct 451 ms 2072 KB Output is correct
6 Correct 468 ms 2388 KB Output is correct
7 Correct 474 ms 2516 KB Output is correct
8 Correct 467 ms 2380 KB Output is correct
9 Correct 482 ms 2352 KB Output is correct
10 Correct 473 ms 2392 KB Output is correct
11 Correct 468 ms 2236 KB Output is correct
12 Correct 486 ms 2380 KB Output is correct
13 Correct 482 ms 2320 KB Output is correct
14 Correct 471 ms 2240 KB Output is correct
15 Correct 482 ms 2324 KB Output is correct
16 Correct 77 ms 596 KB Output is correct
17 Correct 86 ms 948 KB Output is correct
18 Correct 77 ms 772 KB Output is correct
19 Correct 80 ms 664 KB Output is correct
20 Correct 78 ms 740 KB Output is correct
21 Execution timed out 2039 ms 1384 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 664 KB Output is correct
2 Correct 44 ms 868 KB Output is correct
3 Correct 46 ms 852 KB Output is correct
4 Correct 48 ms 852 KB Output is correct
5 Correct 53 ms 852 KB Output is correct
6 Correct 78 ms 648 KB Output is correct
7 Correct 78 ms 812 KB Output is correct
8 Correct 77 ms 852 KB Output is correct
9 Correct 78 ms 760 KB Output is correct
10 Correct 78 ms 852 KB Output is correct
11 Correct 51 ms 768 KB Output is correct
12 Correct 41 ms 808 KB Output is correct
13 Correct 42 ms 848 KB Output is correct
14 Correct 44 ms 848 KB Output is correct
15 Correct 49 ms 848 KB Output is correct
16 Correct 19 ms 604 KB Output is correct
17 Correct 18 ms 488 KB Output is correct
18 Correct 17 ms 856 KB Output is correct
19 Correct 17 ms 600 KB Output is correct
20 Correct 17 ms 604 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 2216 KB Output is correct
2 Correct 454 ms 2128 KB Output is correct
3 Correct 449 ms 2508 KB Output is correct
4 Correct 447 ms 2384 KB Output is correct
5 Correct 451 ms 2072 KB Output is correct
6 Correct 468 ms 2388 KB Output is correct
7 Correct 474 ms 2516 KB Output is correct
8 Correct 467 ms 2380 KB Output is correct
9 Correct 482 ms 2352 KB Output is correct
10 Correct 473 ms 2392 KB Output is correct
11 Correct 468 ms 2236 KB Output is correct
12 Correct 486 ms 2380 KB Output is correct
13 Correct 482 ms 2320 KB Output is correct
14 Correct 471 ms 2240 KB Output is correct
15 Correct 482 ms 2324 KB Output is correct
16 Correct 77 ms 596 KB Output is correct
17 Correct 86 ms 948 KB Output is correct
18 Correct 77 ms 772 KB Output is correct
19 Correct 80 ms 664 KB Output is correct
20 Correct 78 ms 740 KB Output is correct
21 Execution timed out 2039 ms 1384 KB Time limit exceeded
22 Halted 0 ms 0 KB -