Submission #994238

#	Time	Username	Problem	Language	Result	Execution time	Memory
994238		vjudge1	Misspelling (JOI22_misspelling)	C++17	28 / 100	459 ms	1048576 KiB

misspelling

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

ll const M = 1'000'000'007;

struct mod {
    ll v;

    mod() : v(0) {}
    
    mod(ll const x) {
        if (x < M)
            v = x;
        else if (x < 2 * M)
            v = x - M;
        else
            v = x % M;
    }

    mod operator +(mod const& rhs) const {
        return v + rhs.v;
    }

    mod operator +=(mod const& rhs) {
        return *this = *this + rhs;
    }
};

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

    ll n, m;
    cin >> n >> m;

    vector can_change(2, vector(n + 2, vector<char>(n + 1, true)));

    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;

        int banned = 1;

        if (a > b) {
            swap(a, b);
            banned = 0;
        }

        for (int i = a + 1; i <= b; i++) {
            for (int j = a; j >= 0; j--) {
                can_change[banned][i][j] = false;
            }
        }
    }

    vector dp(n + 1, vector(n + 1, vector<mod>(26)));

    for (int c = 0; c < 26; c++)
        dp[1][1][c] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int c = 0; c < 26; c++) {
                for (int d = 0; d < 26; d++) {
                    if (c == d)
                        dp[i + 1][j][d] += dp[i][j][c];
                    else if (c < d) {
                        if (can_change[1][i + 1][j])
                            dp[i + 1][i + 1][d] += dp[i][j][c];
                    }
                    else {
                        if (can_change[0][i + 1][j])
                            dp[i + 1][i + 1][d] += dp[i][j][c];
                    }
                }
            }
        }
    }

    mod ans = 0;

    for (int j = 1; j <= n; j++)
        for (int c = 0; c < 26; c++)
            ans += dp.back()[j][c];

    cout << ans.v << "\n";
}

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