Submission #100185

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100185	2019-03-09T18:44:22 Z	pamaj	Rima (COCI17_rima)	C++14	14 / 140	447 ms	48192 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;

	if(i == j)
	{
		caso1 = solve(i + 1, i + 1);
	}
	else
		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	9 ms	8320 KB	Output is correct
3	Incorrect	9 ms	8320 KB	Output isn't correct
4	Runtime error	111 ms	48192 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	447 ms	22520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	77 ms	18020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	64 ms	17776 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	73 ms	17648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	136 ms	24236 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	84 ms	17880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)