제출 #937089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937089		Pannda	Misspelling (JOI22_misspelling)	C++17	100 / 100	1525 ms	126728 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    static constexpr int P = 1e9 + 7;

    int n, m;
    cin >> n >> m;

    vector<int> enforce0(n, -1); // enforces s[i] >= s[i + 1]
    vector<int> enforce1(n, -1); // enforces s[i] <= s[i + 1]

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if (a < b) enforce0[a] = max(enforce0[a], b);
        else enforce1[b] = max(enforce1[b], a);
    }

    vector<int> all(n);
    iota(all.begin(), all.end(), 0);
    set<int> s0(all.begin(), all.end());
    set<int> s1(all.begin(), all.end());

    vector<vector<int>> dp(n, vector<int>(26, 0));
    dp[n - 1] = vector<int>(26, 1);
    int f = accumulate(dp[n - 1].begin(), dp[n - 1].end(), 0LL) % P;

    for (int i = n - 2; i >= 0; i--) {
        vector<int> adj0;
        vector<int> adj1;
        if (enforce0[i] != -1) {
            while (true) {
                auto it = s0.upper_bound(i);
                if (it == s0.end() || *it > enforce0[i]) break;
                adj0.push_back(*it);
                s0.erase(it);
            }
        }
        if (enforce1[i] != -1) {
            while (true) {
                auto it = s1.upper_bound(i);
                if (it == s1.end() || *it > enforce1[i]) break;
                adj1.push_back(*it);
                s1.erase(it);
            }
        }
        for (int c = 0; c < 26; c++) {
            dp[i][c] = (dp[i][c] + f) % P;
            for (int j : adj0) {
                for (int d = c + 1; d < 26; d++) {
                    dp[i][c] = (dp[i][c] - dp[j][d] + P) % P;
                }
            }
            for (int j : adj1) {
                for (int d = c - 1; d >= 0; d--) {
                    dp[i][c] = (dp[i][c] - dp[j][d] + P) % P;
                }
            }
        }
        f = accumulate(dp[i].begin(), dp[i].end(), 0LL) % P;
    }

    cout << f << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11