oj.uz

답안 #100185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100185 2019-03-09T18:44:22 Z pamaj Rima (COCI17_rima) C++14
14 / 140
 447 ms 48192 KB 
#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

# 결과 실행 시간 메모리 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)