oj.uz

Submission #965421

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

        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++;
                if (i == j){
                    add(dp[layer][j], 1LL * sum * len % MOD);
                }
                for(int t = 2; t <= min(fuck.size() - 1, cnt); ++t){
                    add(dp[layer][j], 1LL * sum * fuck[t] % MOD * C(cnt - 2, t - 2) % 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:141: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]
  141 |     for(int j = 1; j< range.size(); ++j)
      |                    ~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2128 KB Output is correct
2 Correct 85 ms 2072 KB Output is correct
3 Correct 84 ms 2384 KB Output is correct
4 Correct 83 ms 2132 KB Output is correct
5 Correct 85 ms 2132 KB Output is correct
6 Correct 108 ms 2416 KB Output is correct
7 Correct 110 ms 2292 KB Output is correct
8 Correct 110 ms 2368 KB Output is correct
9 Correct 108 ms 2356 KB Output is correct
10 Correct 108 ms 2208 KB Output is correct
11 Correct 108 ms 2388 KB Output is correct
12 Correct 107 ms 2352 KB Output is correct
13 Correct 108 ms 2388 KB Output is correct
14 Correct 109 ms 2432 KB Output is correct
15 Correct 108 ms 2384 KB Output is correct
16 Correct 12 ms 604 KB Output is correct
17 Correct 13 ms 856 KB Output is correct
18 Correct 12 ms 604 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Correct 12 ms 776 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2128 KB Output is correct
2 Correct 85 ms 2072 KB Output is correct
3 Correct 84 ms 2384 KB Output is correct
4 Correct 83 ms 2132 KB Output is correct
5 Correct 85 ms 2132 KB Output is correct
6 Correct 108 ms 2416 KB Output is correct
7 Correct 110 ms 2292 KB Output is correct
8 Correct 110 ms 2368 KB Output is correct
9 Correct 108 ms 2356 KB Output is correct
10 Correct 108 ms 2208 KB Output is correct
11 Correct 108 ms 2388 KB Output is correct
12 Correct 107 ms 2352 KB Output is correct
13 Correct 108 ms 2388 KB Output is correct
14 Correct 109 ms 2432 KB Output is correct
15 Correct 108 ms 2384 KB Output is correct
16 Correct 12 ms 604 KB Output is correct
17 Correct 13 ms 856 KB Output is correct
18 Correct 12 ms 604 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Correct 12 ms 776 KB Output is correct
21 Execution timed out 2048 ms 1244 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 848 KB Output is correct
2 Correct 44 ms 800 KB Output is correct
3 Correct 51 ms 852 KB Output is correct
4 Correct 54 ms 728 KB Output is correct
5 Correct 60 ms 848 KB Output is correct
6 Correct 121 ms 852 KB Output is correct
7 Correct 120 ms 652 KB Output is correct
8 Correct 120 ms 800 KB Output is correct
9 Correct 121 ms 636 KB Output is correct
10 Correct 126 ms 852 KB Output is correct
11 Correct 60 ms 748 KB Output is correct
12 Correct 45 ms 1104 KB Output is correct
13 Correct 48 ms 852 KB Output is correct
14 Correct 49 ms 612 KB Output is correct
15 Correct 57 ms 692 KB Output is correct
16 Correct 22 ms 604 KB Output is correct
17 Correct 18 ms 632 KB Output is correct
18 Correct 20 ms 604 KB Output is correct
19 Correct 19 ms 600 KB Output is correct
20 Correct 21 ms 604 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2128 KB Output is correct
2 Correct 85 ms 2072 KB Output is correct
3 Correct 84 ms 2384 KB Output is correct
4 Correct 83 ms 2132 KB Output is correct
5 Correct 85 ms 2132 KB Output is correct
6 Correct 108 ms 2416 KB Output is correct
7 Correct 110 ms 2292 KB Output is correct
8 Correct 110 ms 2368 KB Output is correct
9 Correct 108 ms 2356 KB Output is correct
10 Correct 108 ms 2208 KB Output is correct
11 Correct 108 ms 2388 KB Output is correct
12 Correct 107 ms 2352 KB Output is correct
13 Correct 108 ms 2388 KB Output is correct
14 Correct 109 ms 2432 KB Output is correct
15 Correct 108 ms 2384 KB Output is correct
16 Correct 12 ms 604 KB Output is correct
17 Correct 13 ms 856 KB Output is correct
18 Correct 12 ms 604 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Correct 12 ms 776 KB Output is correct
21 Execution timed out 2048 ms 1244 KB Time limit exceeded
22 Halted 0 ms 0 KB -