oj.uz

답안 #100168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100168 2019-03-09T18:12:46 Z pamaj Rima (COCI17_rima) C++14
14 / 140
 94 ms 40256 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 20;

int dp[1 << maxn], n;
vector<string> s;

bool rhyme(const string& a, const string& b)
{
	int u = a.size() - 1, v = b.size() - 1;

	int cont = 0;
	while(a[u] == b[v] and u >= 0 and v >= 0)
	{
		cont++, u--, v--;
	}

	if(cont >= max(a.size(), b.size()) - 1) return true;
	return false;
}

int solve(int i, int mask)
{

	if(dp[mask] != -1) return dp[mask];

	int ans = 0;


	for(int j = i + 1; j < n; j++)
	{
		if(i == -1)
		{
			ans = max(ans, solve(j, mask | (1 << j)) + 1);
		}
		else if(rhyme(s[i], s[j]))
		{
			ans = max(ans, solve(j, mask | (1 << j)) + 1);
		}
	}

	return dp[mask] = ans;
}

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

	cout << solve(-1, 0) << "\n";
}

Compilation message

rima.cpp: In function 'bool rhyme(const string&, const string&)':
rima.cpp:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cont >= max(a.size(), b.size()) - 1) return true;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4480 KB Output isn't correct
2 Correct 5 ms 4480 KB Output is correct
3 Incorrect 6 ms 4352 KB Output isn't correct
4 Runtime error 94 ms 40256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 22 ms 14592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 10096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 9952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 9756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 44 ms 16420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 15 ms 9948 KB Execution killed with signal 11 (could be triggered by violating memory limits)