oj.uz

답안 #110388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110388 2019-05-10T18:59:40 Z pamaj Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 18672 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 410;

int n;

bool check(string t)
{
	for(int i = 0; i < t.size(); i++)
		if(t[i] == t[i + 1]) return false;

	return true;
}

map<pair<int, string>, int> dp;

int solve(int num, string s)
{
	if(check(s)) return dp[{num, s}] = num;

	if(dp[{num, s}]) return dp[{num, s}];

	int melhor = 1e9;

	if(num == n) return 1e9;

	for(int i = 0; i < n - 1; i++)
	{
		string temp = s;

		swap(temp[i], temp[i + 1]);

		melhor = min(melhor, solve(num + 1, temp));
	}

	return dp[{num, s}] = melhor;
}

int main()
{
	cin >> n;

	string s;

	cin >> s;

	int ans = solve(0, s);

	cout << (ans == (int)1e9 ? -1 : ans) << "\n";

}

Compilation message

joi2019_ho_t3.cpp: In function 'bool check(std::__cxx11::string)':
joi2019_ho_t3.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++)
                 ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Execution timed out 1062 ms 18672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Execution timed out 1062 ms 18672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Execution timed out 1074 ms 3720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Execution timed out 1062 ms 18672 KB Time limit exceeded
6 Halted 0 ms 0 KB -