oj.uz

Submission #965425

# Submission time Handle Problem Language Result Execution time Memory
965425 2024-04-18T13:56:43 Z steveonalex Boat (APIO16_boat) C++17
9 / 100
 393 ms 4840 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 = s[layer - 1][i - 1];
            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 = s[range.size() - 1][n];
    sub(ans, 1);

    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;
      |                   ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 4088 KB Output is correct
2 Correct 372 ms 4792 KB Output is correct
3 Correct 370 ms 4244 KB Output is correct
4 Correct 373 ms 4232 KB Output is correct
5 Correct 373 ms 4188 KB Output is correct
6 Correct 393 ms 4256 KB Output is correct
7 Correct 370 ms 4264 KB Output is correct
8 Correct 369 ms 4436 KB Output is correct
9 Correct 380 ms 4432 KB Output is correct
10 Correct 390 ms 4432 KB Output is correct
11 Correct 383 ms 4332 KB Output is correct
12 Correct 381 ms 4244 KB Output is correct
13 Correct 371 ms 4332 KB Output is correct
14 Correct 374 ms 4840 KB Output is correct
15 Correct 378 ms 4420 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 71 ms 2652 KB Output is correct
18 Correct 68 ms 2648 KB Output is correct
19 Correct 71 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 4088 KB Output is correct
2 Correct 372 ms 4792 KB Output is correct
3 Correct 370 ms 4244 KB Output is correct
4 Correct 373 ms 4232 KB Output is correct
5 Correct 373 ms 4188 KB Output is correct
6 Correct 393 ms 4256 KB Output is correct
7 Correct 370 ms 4264 KB Output is correct
8 Correct 369 ms 4436 KB Output is correct
9 Correct 380 ms 4432 KB Output is correct
10 Correct 390 ms 4432 KB Output is correct
11 Correct 383 ms 4332 KB Output is correct
12 Correct 381 ms 4244 KB Output is correct
13 Correct 371 ms 4332 KB Output is correct
14 Correct 374 ms 4840 KB Output is correct
15 Correct 378 ms 4420 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 71 ms 2652 KB Output is correct
18 Correct 68 ms 2648 KB Output is correct
19 Correct 71 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct
21 Incorrect 69 ms 4192 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 4088 KB Output is correct
2 Correct 372 ms 4792 KB Output is correct
3 Correct 370 ms 4244 KB Output is correct
4 Correct 373 ms 4232 KB Output is correct
5 Correct 373 ms 4188 KB Output is correct
6 Correct 393 ms 4256 KB Output is correct
7 Correct 370 ms 4264 KB Output is correct
8 Correct 369 ms 4436 KB Output is correct
9 Correct 380 ms 4432 KB Output is correct
10 Correct 390 ms 4432 KB Output is correct
11 Correct 383 ms 4332 KB Output is correct
12 Correct 381 ms 4244 KB Output is correct
13 Correct 371 ms 4332 KB Output is correct
14 Correct 374 ms 4840 KB Output is correct
15 Correct 378 ms 4420 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 71 ms 2652 KB Output is correct
18 Correct 68 ms 2648 KB Output is correct
19 Correct 71 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct
21 Incorrect 69 ms 4192 KB Output isn't correct
22 Halted 0 ms 0 KB -