oj.uz

답안 #100182

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

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