Submission #1178521

#TimeUsernameProblemLanguageResultExecution timeMemory
1178521tch1cherinMisspelling (JOI22_misspelling)C++20
8 / 100
4094 ms80836 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...