Submission #594893

#	Time	Username	Problem	Language	Result	Execution time	Memory
594893		jwvg0425	Misspelling (JOI22_misspelling)	C++17	0 / 100	108 ms	42564 KiB

misspelling

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <array>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9 + 7)

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int n, m;
i64 table[35][205][205];
vector<ii> conds[205];

i64 solve(int pch, int l, int r)
{
	if (r == n + 1)
		return 1;

	auto& res = table[pch][l][r];

	if (res != -1)
		return res;

	// 똑같이 유지한 경우
	res = solve(pch, l, r + 1);

	// 바꾸는 경우. l 이후에서 시작하고 r포함하는 조건들을 봐야 한다
	int up = 0, down = 0;
	for (int cl = l + 1; cl <= r; cl++)
	{
		for (auto& c : conds[cl])
		{
			if (c.xx < r)
				continue;

			if (c.yy > 0)
				up++;
			else
				down++;
		}
	}

	if (up > 0 && down > 0)
		return res;

	if (up > 0)
	{
		for (int nch = pch + 1; nch < 26; nch++)
			res = (res + solve(nch, r, r + 1)) % MOD;
	}

	if (down > 0)
	{
		for (int nch = 0; nch < pch; nch++)
			res = (res + solve(nch, r, r + 1)) % MOD;
	}

	return res;
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		if (a < b)
			conds[a + 1].emplace_back(b, -1);
		else
			conds[b + 1].emplace_back(a, 1);
	}

	memset(table, -1, sizeof(table));

	i64 ans = 0;
	for (int ch = 0; ch < 26; ch++)
		ans = (ans + solve(ch, 1, 2)) % MOD;

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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