Submission #835974

#	Time	Username	Problem	Language	Result	Execution time	Memory
835974		PurpleCrayon	Misspelling (JOI22_misspelling)	C++17	28 / 100	4042 ms	12408 KiB

misspelling

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e5+10, MOD = 1e9+7;
const int K = 26;

void add_self(int& a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int n, m;
int last_one[N], last_two[N], dp[N][K];

void solve() {
    cin >> n >> m;
    memset(last_one, -1, sizeof(last_one));
    memset(last_two, -1, sizeof(last_two));
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b, --a, --b;
        if (a < b) {
            last_one[a] = max(last_one[a], b);
        } else {
            last_two[b] = max(last_two[b], a);
        }
    }

    for (int i = n-1; i >= 0; i--) {
        for (int j = K-1; j >= 0; j--) {
            int mx_one = -1, mx_two = -1;
            for (int r = i; r < n; r++) {
                mx_one = max(mx_one, last_one[r]);
                mx_two = max(mx_two, last_two[r]);

                if (r == n-1) {
                    add_self(dp[i][j], 1);
                    continue;
                }

                if (mx_one <= r && mx_two <= r) {
                    for (int nxt = 0; nxt < K; nxt++) if (nxt != j)
                        add_self(dp[i][j], dp[r+1][nxt]);
                } else if (mx_one <= r) { // i need to be greater than the next one
                    for (int nxt = 0; nxt < j; nxt++)
                        add_self(dp[i][j], dp[r+1][nxt]);
                } else if (mx_two <= r) {
                    for (int nxt = j + 1; nxt < K; nxt++)
                        add_self(dp[i][j], dp[r+1][nxt]);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < K; i++) add_self(ans, dp[0][i]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    solve();
}

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