Submission #1178521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178521		tch1cherin	Misspelling (JOI22_misspelling)	C++20	8 / 100	4094 ms	80836 KiB

misspelling

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

constexpr int MOD = 1e9 + 7;
constexpr int K = 26;

int add(int a, int b) {
  return a + b < MOD ? a + b : a + b - MOD;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    --A[i], --B[i];
  }
  vector<int> S;
  int answer = 0;
  auto Gen = [&](auto&& self, int pos, int cur) -> void {
    S.push_back(cur);
    if (pos + 1 == N) {
      bool good = true;
      for (int i = 0; i < M; i++) {
        vector<int> T_a = S, T_b = S;
        T_a.erase(T_a.begin() + A[i]);
        T_b.erase(T_b.begin() + B[i]);
        if (T_a > T_b) {
          good = false;
          break;
        }
      }
      if (good) {
        vector<vector<int>> DP(N, vector<int>(K));
        DP[0] = vector<int>(K, 1);
        for (int i = 0; i < N - 1; i++) {
          if (S[i] < S[i + 1]) {
            for (int j = 0; j < K; j++) {
              for (int k = j + 1; k < K; k++) {
                DP[i + 1][k] = add(DP[i + 1][k], DP[i][j]);
              }
            }
          } else if (S[i] == S[i + 1]) {
            for (int j = 0; j < K; j++) {
              DP[i + 1][j] = add(DP[i + 1][j], DP[i][j]);
            }
          } else {
            for (int j = 0; j < K; j++) {
              for (int k = 0; k < j; k++) {
                DP[i + 1][k] = add(DP[i + 1][k], DP[i][j]);
              }
            }
          }
        }
        for (int i = 0; i < K; i++) {
          answer = add(answer, DP[N - 1][i]);
        }
      }
      S.pop_back();
      return;
    }
    for (int i = -1; i <= 1; i++) {
      self(self, pos + 1, cur + i);
    }
    S.pop_back();
  };
  Gen(Gen, 0, 0);
  cout << answer << "\n";
}

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