oj.uz

답안 #100191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100191 2019-03-09T19:13:07 Z pamaj Rima (COCI17_rima) C++14
42 / 140
 255 ms 188076 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 19;

#define int long long

int dp[1 << 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 mask, int last)
{
	if(dp[mask][last] != -1) return dp[mask][last];

	
	int ans = __builtin_popcount(mask);
	for(int i = 0; i < n; i++)
	{
		if(mask & (1 << i)) continue;

		if(rhyme(s[i], s[last]))
		{
			ans = max(ans, solve(mask | (1 << i), i));
		}
	}

	//string a;

	// int aux = mask;
	// while(aux)
	// {
	// 	a += aux % 2 + '0';

	// 	aux /= 2;
	// }

	// reverse(a.begin(), a.end());

	//cout << a << "\n";

	return dp[mask][last] = ans;
}

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(0, i));
	}

	cout << ans << "\n";
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 78328 KB Output is correct
2 Correct 60 ms 78328 KB Output is correct
3 Correct 75 ms 78328 KB Output is correct
4 Runtime error 255 ms 188076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 160 ms 162424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 147 ms 157928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 146 ms 157752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 151 ms 157488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 162 ms 164108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 146 ms 157780 KB Execution killed with signal 11 (could be triggered by violating memory limits)