제출 #1256095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256095		LucaLucaM	Misspelling (JOI22_misspelling)	C++20	28 / 100	72 ms	43332 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::vector<int>> gpos(n + 2), gneg(n + 2);
  
  for (int i = 0; i < m; i++) {
    int a, b;
    std::cin >> a >> b;
    if (a < b) {
      gneg[a + 1].push_back(b);
    } else if (b < a) {
      gpos[b + 1].push_back(a);
    }
  }

  std::vector<int> fpos(n + 1, 0);
  std::vector<int> fneg(n + 1, 0);

  for (int i = n; i > 0; i--) {
    for (int x = 0; x < SIGMA; x++) {
      dp[i][x] = 1;
    }
    
    for (int j : gpos[i + 1]) {
      for (int p = i + 1; p <= j; p++) {
        fpos[p]++;
      }
    }
    for (int j : gneg[i + 1]) {
      for (int p = i + 1; p <= j; p++) {
        fneg[p]++;
      }
    }

    for (int j = i + 1; j <= n; j++) {
      if (!fpos[j] || !fneg[j]) {
        if (!fpos[j] && !fneg[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 (!fpos[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