oj.uz

Submission #499711

# Submission time Handle Problem Language Result Execution time Memory
499711 2021-12-29T09:53:13 Z Stickfish Boat (APIO16_boat) C++17
0 / 100
 7 ms 4148 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 = {0};
    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] << endl;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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