제출 #499713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499713		Stickfish	Boat (APIO16_boat)	C++17	9 / 100	7 ms	4236 KiB

boat

#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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42