Submission #100183

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100183	2019-03-09T18:41:29 Z	pamaj	Rima (COCI17_rima)	C++14	14 / 140	484 ms	48256 KB

rima

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

const int maxn = 1e3 + 10;

#define int long long

int dp[maxn][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 i, int j)
{
	if(dp[i][j] != -1) return dp[i][j];

	if(i == n) return 0;

	int caso1 = solve(i + 1, j);
	int caso2;

	if(rhyme(s[i],s[j]))
	{
		caso2 = solve(i + 1, i) + 1;
	}
	else 
		caso2 = 0;


	return dp[i][j] = max(caso1, caso2);
}

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));

	int ans = 0;

	for(int i = 0; i < n; i++)
		ans = max(ans, solve(i, i));

	cout << ans << "\n";
}

Subtask #1

14.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	8320 KB	Output isn't correct
2	Correct	8 ms	8320 KB	Output is correct
3	Incorrect	8 ms	8320 KB	Output isn't correct
4	Runtime error	120 ms	48256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	484 ms	22620 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	86 ms	18020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	75 ms	17760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	74 ms	17584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	131 ms	24392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	96 ms	17756 KB	Execution killed with signal 11 (could be triggered by violating memory limits)