oj.uz

Submission #100188

# Submission time Handle Problem Language Result Execution time Memory
100188 2019-03-09T19:03:56 Z pamaj Rima (COCI17_rima) C++14
14 / 140
 77 ms 20176 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 19;

#define int long long

int dp[1 << maxn], n;
vector<string> s;

bool rhyme(const string& a, const string& b)
{
	int u = (int)a.size() - 1, v = (int)b.size() - 1;

	int cont = 0;
	while(a[u] == b[v] and u >= 0 and v >= 0)
	{
		cont++, u--, v--;
	}

	if(cont >= max((int)a.size(), (int)b.size()) - 1) return true;
	return false;
}

int solve(int mask)
{
	if(dp[mask] != -1) return dp[mask];

	int ff = -1;

	bool ok = true;

	for(int i = 0; i < n; i++)
	{
		if(mask & (1 << i))
		{
			if(ff == -1)
				ff = i;
			else
			{
				if(!rhyme(s[i], s[ff]))
				{
					ok = false;
					break;
				}

				ff = i;

			}
		}
	}

	if(!ok) return 0;

	if(mask == (1 << n) - 1) return n;

	int ans = __builtin_popcount(mask);
	for(int i = 0; i < n; i++)
	{
		if(mask & (1 << i)) continue;

		ans = max(ans, solve(mask | (1 << i)));
	}

	//string a;

	// int aux = mask;
	// while(aux)
	// {
	// 	a += aux % 2 + '0';

	// 	aux /= 2;
	// }

	// reverse(a.begin(), a.end());

	//cout << a << "\n";

	return dp[mask] = ans;
}

int32_t main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n;

	for(int i = 0; i < n; i++)
	{
		string a;
		cin >> a;
		s.push_back(a);
	}

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

	cout << solve(0) << "\n";

}

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4480 KB Output isn't correct
2 Correct 8 ms 4480 KB Output is correct
3 Incorrect 6 ms 4480 KB Output isn't correct
4 Incorrect 77 ms 20176 KB Output isn't correct
5 Runtime error 23 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 15 ms 10352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 9832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 27 ms 16336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 9820 KB Execution killed with signal 11 (could be triggered by violating memory limits)