oj.uz

Submission #499713

# Submission time Handle Problem Language Result Execution time Memory
499713 2021-12-29T09:56:37 Z Stickfish Boat (APIO16_boat) C++17
9 / 100
 7 ms 4236 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;
const int MAXN = 502;
ll dp__[MAXN][MAXN * 2];
ll* dp_[MAXN];
ll** dp = dp_ + 1;
ll a[MAXN];
ll b[MAXN];

signed main() {
    for (int i = 0; i < MAXN; ++i)
        dp_[i] = dp__[i] + 1;
    int n;
    cin >> n;
    vector<ll> cpr = {0};
    vector<ll> sz;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        ++b[i];
        cpr.push_back(a[i]);
        cpr.push_back(b[i]);
    }
    sort(cpr.begin(), cpr.end());
    cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin());
    int m = cpr.size();
    for (int i = 0; i + 1 < m; ++i) {
        sz.push_back(cpr[i + 1] - cpr[i]);
    }
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin();
        b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin();
    }
    for (int i = 0; i < m; ++i)
        dp[-1][i] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = a[i]; j < b[i]; ++j) {
            dp[i][j] = (dp[i - 1][j - 1] * sz[j]) % MOD;
        }
        for (int j = 0; j < m; ++j) {
            dp[i][j] += dp[i][j - 1];
            dp[i][j] %= MOD;
        }
        for (int j = 0; j < m; ++j) {
            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= MOD;
        }
    }
    //for (int i = 0; i < n; ++i) {
        //for (int j = 0; j < m; ++j)
            //cout << dp[i][j] << ' ';
        //cout << endl;
    //}
    cout << dp[n - 1][m - 1] - 1 << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4184 KB Output is correct
2 Correct 6 ms 4140 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 6 ms 4136 KB Output is correct
5 Correct 6 ms 4172 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 6 ms 4172 KB Output is correct
8 Correct 6 ms 4172 KB Output is correct
9 Correct 6 ms 4156 KB Output is correct
10 Correct 6 ms 4172 KB Output is correct
11 Correct 7 ms 4220 KB Output is correct
12 Correct 6 ms 4172 KB Output is correct
13 Correct 7 ms 4172 KB Output is correct
14 Correct 7 ms 4160 KB Output is correct
15 Correct 6 ms 4172 KB Output is correct
16 Correct 2 ms 3020 KB Output is correct
17 Correct 3 ms 3008 KB Output is correct
18 Correct 3 ms 3020 KB Output is correct
19 Correct 3 ms 3008 KB Output is correct
20 Correct 3 ms 3008 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4184 KB Output is correct
2 Correct 6 ms 4140 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 6 ms 4136 KB Output is correct
5 Correct 6 ms 4172 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 6 ms 4172 KB Output is correct
8 Correct 6 ms 4172 KB Output is correct
9 Correct 6 ms 4156 KB Output is correct
10 Correct 6 ms 4172 KB Output is correct
11 Correct 7 ms 4220 KB Output is correct
12 Correct 6 ms 4172 KB Output is correct
13 Correct 7 ms 4172 KB Output is correct
14 Correct 7 ms 4160 KB Output is correct
15 Correct 6 ms 4172 KB Output is correct
16 Correct 2 ms 3020 KB Output is correct
17 Correct 3 ms 3008 KB Output is correct
18 Correct 3 ms 3020 KB Output is correct
19 Correct 3 ms 3008 KB Output is correct
20 Correct 3 ms 3008 KB Output is correct
21 Incorrect 6 ms 4144 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4184 KB Output is correct
2 Correct 6 ms 4140 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 6 ms 4136 KB Output is correct
5 Correct 6 ms 4172 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 6 ms 4172 KB Output is correct
8 Correct 6 ms 4172 KB Output is correct
9 Correct 6 ms 4156 KB Output is correct
10 Correct 6 ms 4172 KB Output is correct
11 Correct 7 ms 4220 KB Output is correct
12 Correct 6 ms 4172 KB Output is correct
13 Correct 7 ms 4172 KB Output is correct
14 Correct 7 ms 4160 KB Output is correct
15 Correct 6 ms 4172 KB Output is correct
16 Correct 2 ms 3020 KB Output is correct
17 Correct 3 ms 3008 KB Output is correct
18 Correct 3 ms 3020 KB Output is correct
19 Correct 3 ms 3008 KB Output is correct
20 Correct 3 ms 3008 KB Output is correct
21 Incorrect 6 ms 4144 KB Output isn't correct
22 Halted 0 ms 0 KB -