Submission #100168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100168	2019-03-09T18:12:46 Z	pamaj	Rima (COCI17_rima)	C++14	14 / 140	94 ms	40256 KB

rima

#include <bits/stdc++.h>
using namespace std;

const int maxn = 20;

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

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

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

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

int solve(int i, int mask)
{

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

	int ans = 0;


	for(int j = i + 1; j < n; j++)
	{
		if(i == -1)
		{
			ans = max(ans, solve(j, mask | (1 << j)) + 1);
		}
		else if(rhyme(s[i], s[j]))
		{
			ans = max(ans, solve(j, mask | (1 << j)) + 1);
		}
	}

	return dp[mask] = ans;
}

int 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(-1, 0) << "\n";
}

Compilation message

rima.cpp: In function 'bool rhyme(const string&, const string&)':
rima.cpp:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cont >= max(a.size(), b.size()) - 1) return true;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	4480 KB	Output isn't correct
2	Correct	5 ms	4480 KB	Output is correct
3	Incorrect	6 ms	4352 KB	Output isn't correct
4	Runtime error	94 ms	40256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	22 ms	14592 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	14 ms	10096 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	14 ms	9952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	13 ms	9756 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	44 ms	16420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	15 ms	9948 KB	Execution killed with signal 11 (could be triggered by violating memory limits)