oj.uz

답안 #234963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234963 2020-05-26T12:52:07 Z davitmarg Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048576 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 402;

int pr[3][N], n, dp[N][N][N][3],val[N][N][N][3];
vector<int> pos[3];
string s;

int ind(char x)
{
	if (x == 'R')
		return 0;
	if (x == 'G')
		return 1;
	return 2;
}

int get(int i, int l, int r)
{
	return max(0, pr[i][r] - pr[i][l - 1]);
}

void calc(int x,int a, int b, int c)
{
	a++;
	b++;
	c++;

	int p;
	if (x == 0)
		p = a;
	else if (x == 1)
		p = b;
	else
		p = c;

	int res = 0;
	if (p > pos[x].size())
	{
		val[a - 1][b - 1][c - 1][x] = mod;
		return;
	}

	if (x != 0 && a <= pos[0].size())
		res += get(0, pos[0][a - 1], pos[x][p - 1]);
	if (x != 1 && b <= pos[1].size())
		res += get(1, pos[1][b - 1], pos[x][p - 1]);
	if (x != 2 && c <= pos[2].size())
		res += get(2, pos[2][c - 1], pos[x][p - 1]);
	val[a - 1][b - 1][c - 1][x] = res;
}

int main()
{
	fastIO;
	cin >> n;
	cin >> s;
	s = "#" + s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
			pr[j][i] = pr[j][i - 1];
		pr[ind(s[i])][i]++;
		pos[ind(s[i])].push_back(i);
	}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++)
			{
				calc(i, j, k, 0);
				calc(i, j, k, 1);
				calc(i, j, k, 2);
				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = mod;
			}

	
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int k = 0; k < n; k++)
		for (int a = 0; a <= k && a <= pos[0].size(); a++)
			for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
			{
				int c = k - a - b;

				for (int i = 0; i < 3; i++)
					for (int j = 0; j < 3; j++)
					{
						if (i == j)
							continue;
						dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j] = min(dp[a][b][c][i] + val[a][b][c][j], dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j]);
					}
			}

	int ans = min(dp[pr[0][n]][pr[1][n]][pr[2][n]][0], min(dp[pr[0][n]][pr[1][n]][pr[2][n]][1], dp[pr[0][n]][pr[1][n]][pr[2][n]][2]));
	if (ans == mod)
		ans = -1;
	cout << ans << endl;
	
	return 0;
}

/*




*/

Compilation message

joi2019_ho_t3.cpp: In function 'void calc(int, int, int, int)':
joi2019_ho_t3.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (p > pos[x].size())
      ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 0 && a <= pos[0].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 1 && b <= pos[1].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 2 && c <= pos[2].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:104:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int a = 0; a <= k && a <= pos[0].size(); a++)
                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:105:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
                                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Runtime error 38 ms 1680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Runtime error 38 ms 1680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Runtime error 963 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Runtime error 38 ms 1680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -