oj.uz

Submission #556551

# Submission time Handle Problem Language Result Execution time Memory
556551 2022-05-03T10:39:43 Z InternetPerson10 Boat (APIO16_boat) C++17
0 / 100
 44 ms 46424 KB 
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MOD = 1e9 + 7;

ll binom[2002][2002];

void precalc() {
    binom[0][0] = 1;
    for(int i = 1; i <= 2000; i++) {
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % MOD;
        }
    }
}

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])) {
                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;
                continue;
            }
            ll siz = nums[j] - nums[j-1];
            ans[i][j] = siz;
            ans[i][j] += siz * pref[i-1][j-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++;
                    ans[i][j] += (binom[siz+1][g] - (siz+1) + MOD) * (1 + pref[k-1][j-1]);
                    ans[i][j] %= MOD;
                }
            }
            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: In function 'int main()':
boat.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 1; j < nums.size(); j++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28776 KB Output is correct
2 Correct 18 ms 28756 KB Output is correct
3 Correct 20 ms 28784 KB Output is correct
4 Correct 19 ms 28752 KB Output is correct
5 Correct 18 ms 28756 KB Output is correct
6 Correct 19 ms 29004 KB Output is correct
7 Correct 20 ms 28908 KB Output is correct
8 Correct 18 ms 28840 KB Output is correct
9 Correct 20 ms 28944 KB Output is correct
10 Correct 20 ms 28940 KB Output is correct
11 Correct 19 ms 28884 KB Output is correct
12 Correct 19 ms 28908 KB Output is correct
13 Correct 19 ms 28884 KB Output is correct
14 Correct 19 ms 28928 KB Output is correct
15 Correct 20 ms 28900 KB Output is correct
16 Incorrect 15 ms 27604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28776 KB Output is correct
2 Correct 18 ms 28756 KB Output is correct
3 Correct 20 ms 28784 KB Output is correct
4 Correct 19 ms 28752 KB Output is correct
5 Correct 18 ms 28756 KB Output is correct
6 Correct 19 ms 29004 KB Output is correct
7 Correct 20 ms 28908 KB Output is correct
8 Correct 18 ms 28840 KB Output is correct
9 Correct 20 ms 28944 KB Output is correct
10 Correct 20 ms 28940 KB Output is correct
11 Correct 19 ms 28884 KB Output is correct
12 Correct 19 ms 28908 KB Output is correct
13 Correct 19 ms 28884 KB Output is correct
14 Correct 19 ms 28928 KB Output is correct
15 Correct 20 ms 28900 KB Output is correct
16 Incorrect 15 ms 27604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 46424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28776 KB Output is correct
2 Correct 18 ms 28756 KB Output is correct
3 Correct 20 ms 28784 KB Output is correct
4 Correct 19 ms 28752 KB Output is correct
5 Correct 18 ms 28756 KB Output is correct
6 Correct 19 ms 29004 KB Output is correct
7 Correct 20 ms 28908 KB Output is correct
8 Correct 18 ms 28840 KB Output is correct
9 Correct 20 ms 28944 KB Output is correct
10 Correct 20 ms 28940 KB Output is correct
11 Correct 19 ms 28884 KB Output is correct
12 Correct 19 ms 28908 KB Output is correct
13 Correct 19 ms 28884 KB Output is correct
14 Correct 19 ms 28928 KB Output is correct
15 Correct 20 ms 28900 KB Output is correct
16 Incorrect 15 ms 27604 KB Output isn't correct
17 Halted 0 ms 0 KB -