제출 #1184085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184085		mfmme23	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1'000'000'007;

int main() {
    int N;
    cin >> N;

    vector<pair<int, int>> events(N);
    vector<pair<int, int>> seq(2 * N);  // arrival and departure
    for (int i = 0; i < N; ++i) {
        cin >> events[i].first >> events[i].second;
        seq[events[i].first - 1] = {i, 1};  // arrival
        seq[events[i].second - 1] = {i, -1}; // departure
    }

    vector<vector<int>> dp(2 * N + 1, vector<int>(2 * N + 1, 0));
    for (int i = 0; i <= 2 * N; ++i)
        dp[i][i] = 1;  // base case: empty segment

    for (int len = 2; len <= 2 * N; len += 2) {
        for (int l = 0; l + len <= 2 * N; ++l) {
            int r = l + len;
            for (int m = l + 1; m < r; m += 2) {
                if (seq[l].second == 1 && seq[m].second == -1 && seq[l].first == seq[m].first) {
                    int left = dp[l + 1][m];
                    int right = dp[m + 1][r];
                    dp[l][r] = (dp[l][r] + 1LL * left * right % MOD) % MOD;
                }
            }
        }
    }

    cout << dp[0][2 * N] << endl;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22