oj.uz

Submission #556591

# Submission time Handle Problem Language Result Execution time Memory
556591 2022-05-03T11:47:49 Z InternetPerson10 Boat (APIO16_boat) C++17
36 / 100
 2000 ms 6324 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll MOD = 1e9 + 7;

ll modpow(ll n, ll e) {
    if(e == 0) return 1;
    ll x = modpow(n, e/2);
    x *= x; x %= MOD;
    if(e%2) {
        x *= n;
        x %= MOD;
    }
    return x;
}

ll modinv(ll n) {
    return modpow(n, MOD - 2);
}

ll fact[5001];
ll invfact[5001];

ll binom(ll n, ll k) { // Assumes k is quite small
    if(k > n) return 0;
    if(k == n) return 1;
    ll ans = 1;
    if(n-k <= 5000) {
        ans = fact[n];
        ans *= invfact[n-k];
        ans %= MOD;
    }
    else {
        for(ll i = n-k+1; i <= n; i++) {
            ans *= i;
            ans %= MOD;
        }
    }
    ans *= invfact[k];
    ans %= MOD;
    return ans;
}

void precalc() {
    fact[0] = 1;
    for(int i = 1; i <= 5000; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    for(int i = 0; i <= 5000; i++) {
        invfact[i] = modinv(fact[i]);
    }
}

ll ans[501][1001], pref[501][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precalc();
    int n;
    cin >> n;
    vector<int> nums(2 * n), a(n+1), b(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        b[i]++;
        nums[2*i - 2] = a[i];
        nums[2*i - 1] = b[i];
    }
    sort(nums.begin(), nums.end());
    nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < nums.size(); j++) {
            if(!(a[i] <= nums[j-1] && nums[j] <= b[i])) {
                continue;
            }
            ll siz = nums[j] - nums[j-1];
            ans[i][j] += siz * (pref[i-1][j-1] + 1);
            ans[i][j] %= MOD;
            int g = 1;
            for(int k = i-1; k > 0; k--) {
                if(a[k] <= nums[j-1] && nums[j] <= b[k]) {
                    g++;
                    ll x = siz;
                    for(int l = 2; l <= g; l++) {
                        x *= siz-l+1;
                        x %= MOD;
                        x *= modinv(l);
                        x %= MOD;
                        ans[i][j] += ((x * binom(g-2, l-2)) % MOD) * (1 + pref[k-1][j-1]);
                        ans[i][j] %= MOD;
                    }
                }
            }
        }
        for(int j = 1; j < nums.size(); j++) {
            pref[i][j] += ans[i][j] + pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1];
            pref[i][j] += MOD;
            pref[i][j] %= MOD;
        }
    }
    cout << pref[n][nums.size()-1] << endl;
}

Compilation message

boat.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
boat.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
boat.cpp: In function 'int main()':
boat.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j = 1; j < nums.size(); j++) {
      |                        ~~^~~~~~~~~~~~~
boat.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j = 1; j < nums.size(); j++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6100 KB Output is correct
2 Correct 12 ms 6228 KB Output is correct
3 Correct 11 ms 6228 KB Output is correct
4 Correct 10 ms 6144 KB Output is correct
5 Correct 11 ms 6228 KB Output is correct
6 Correct 12 ms 6228 KB Output is correct
7 Correct 11 ms 6292 KB Output is correct
8 Correct 14 ms 6228 KB Output is correct
9 Correct 13 ms 6228 KB Output is correct
10 Correct 13 ms 6324 KB Output is correct
11 Correct 12 ms 6228 KB Output is correct
12 Correct 12 ms 6268 KB Output is correct
13 Correct 11 ms 6232 KB Output is correct
14 Correct 11 ms 6284 KB Output is correct
15 Correct 10 ms 6228 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 6 ms 5076 KB Output is correct
18 Correct 7 ms 5076 KB Output is correct
19 Correct 7 ms 5076 KB Output is correct
20 Correct 7 ms 5076 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6100 KB Output is correct
2 Correct 12 ms 6228 KB Output is correct
3 Correct 11 ms 6228 KB Output is correct
4 Correct 10 ms 6144 KB Output is correct
5 Correct 11 ms 6228 KB Output is correct
6 Correct 12 ms 6228 KB Output is correct
7 Correct 11 ms 6292 KB Output is correct
8 Correct 14 ms 6228 KB Output is correct
9 Correct 13 ms 6228 KB Output is correct
10 Correct 13 ms 6324 KB Output is correct
11 Correct 12 ms 6228 KB Output is correct
12 Correct 12 ms 6268 KB Output is correct
13 Correct 11 ms 6232 KB Output is correct
14 Correct 11 ms 6284 KB Output is correct
15 Correct 10 ms 6228 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 6 ms 5076 KB Output is correct
18 Correct 7 ms 5076 KB Output is correct
19 Correct 7 ms 5076 KB Output is correct
20 Correct 7 ms 5076 KB Output is correct
21 Execution timed out 2090 ms 2232 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 1408 KB Output is correct
2 Correct 239 ms 1516 KB Output is correct
3 Correct 354 ms 1340 KB Output is correct
4 Correct 423 ms 1340 KB Output is correct
5 Correct 509 ms 1324 KB Output is correct
6 Correct 1766 ms 1448 KB Output is correct
7 Correct 1785 ms 1444 KB Output is correct
8 Correct 1788 ms 1412 KB Output is correct
9 Correct 1781 ms 1476 KB Output is correct
10 Correct 1762 ms 1508 KB Output is correct
11 Correct 518 ms 1376 KB Output is correct
12 Correct 273 ms 1280 KB Output is correct
13 Correct 413 ms 1292 KB Output is correct
14 Correct 387 ms 1368 KB Output is correct
15 Correct 497 ms 1436 KB Output is correct
16 Correct 317 ms 1368 KB Output is correct
17 Correct 222 ms 1356 KB Output is correct
18 Correct 280 ms 1376 KB Output is correct
19 Correct 211 ms 1288 KB Output is correct
20 Correct 328 ms 1284 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6100 KB Output is correct
2 Correct 12 ms 6228 KB Output is correct
3 Correct 11 ms 6228 KB Output is correct
4 Correct 10 ms 6144 KB Output is correct
5 Correct 11 ms 6228 KB Output is correct
6 Correct 12 ms 6228 KB Output is correct
7 Correct 11 ms 6292 KB Output is correct
8 Correct 14 ms 6228 KB Output is correct
9 Correct 13 ms 6228 KB Output is correct
10 Correct 13 ms 6324 KB Output is correct
11 Correct 12 ms 6228 KB Output is correct
12 Correct 12 ms 6268 KB Output is correct
13 Correct 11 ms 6232 KB Output is correct
14 Correct 11 ms 6284 KB Output is correct
15 Correct 10 ms 6228 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 6 ms 5076 KB Output is correct
18 Correct 7 ms 5076 KB Output is correct
19 Correct 7 ms 5076 KB Output is correct
20 Correct 7 ms 5076 KB Output is correct
21 Execution timed out 2090 ms 2232 KB Time limit exceeded
22 Halted 0 ms 0 KB -