oj.uz

답안 #100183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100183 2019-03-09T18:41:29 Z pamaj Rima (COCI17_rima) C++14
14 / 140
 484 ms 48256 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 = 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 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)