Submission #100182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100182	2019-03-09T18:35:33 Z	pamaj	Rima (COCI17_rima)	C++14	14 / 140	605 ms	40128 KB

rima

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

const int maxn = 1e3 + 10;

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

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

	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	5 ms	4352 KB	Output isn't correct
2	Correct	6 ms	4352 KB	Output is correct
3	Incorrect	5 ms	4352 KB	Output isn't correct
4	Runtime error	114 ms	40128 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	605 ms	14584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	93 ms	10128 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	88 ms	9836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	79 ms	9648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	151 ms	16312 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	98 ms	9764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)