Submission #1256094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256094		LucaLucaM	Misspelling (JOI22_misspelling)	C++20	28 / 100	45 ms	5308 KiB

misspelling

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

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int mod = 1e9 + 7;
const int MAXN = 200;
const int SIGMA = 26;

int dp[MAXN + 1][SIGMA];

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n, m;
  std::cin >> n >> m;

  std::vector<std::pair<int, int>> pos, neg;

  for (int i = 0; i < m; i++) {
    int a, b;
    std::cin >> a >> b;
    if (a < b) {
      neg.push_back({a + 1, b});
    } else if (b < a) {
      pos.push_back({b + 1, a});
    }
  }

  auto positive = [&](int i, int j) {
    i++;
    for (const auto &[l, r] : pos) {
      if (i <= l && l <= j && r >= j) {
        return true;
      }
    }
    return false;
  };
  auto negative = [&](int i, int j) {
    i++;
    for (const auto &[l, r] : neg) {
      if (i <= l && l <= j && r >= j) {
        return true;
      }
    }
    return false;
  };

  for (int i = n; i > 0; i--) {
    for (int x = 0; x < SIGMA; x++) {
      dp[i][x] = 1;
    }
    for (int j = i + 1; j <= n; j++) {
      if (!positive(i, j) || !negative(i, j)) {
        if (!positive(i, j) && !negative(i, j)) { // fac orice
          for (int x = 0; x < SIGMA; x++) {
            for (int y = 0; y < SIGMA; y++) {
              if (x != y) {
                dp[i][x] += dp[j][y];
                dp[i][x] %= mod;
              }
            }
          }
        } else {
          if (positive(i, j)) {
            for (int x = 0; x < SIGMA; x++) {
              for (int y = x + 1; y < SIGMA; y++) {
                dp[i][x] += dp[j][y];
                dp[i][x] %= mod;
              }
            }
          } else {
            for (int x = 0; x < SIGMA; x++) {
              for (int y = 0; y < x; y++) {
                dp[i][x] += dp[j][y];
                dp[i][x] %= mod;
              }
            }
          }
        }
      }
    }
  }

  ll answer = 0;
  for (int i = 0; i < SIGMA; i++) {
    answer += dp[1][i];
  }
  std::cout << answer % mod;
  
  return 0;
}

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