Submission #120118

#	Time	Username	Problem	Language	Result	Execution time	Memory
120118		antimirage	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	181 ms	163804 KiB

joi2019_ho_t3

/**
	GOT A FEELING THAT I"M GOING UNDER
**/
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 405;

int dp[N][N][N][3], n, in[3][N], cnt[3], cn[3][2][N][N];

string s;

inline int min(int a, int b) {
	return a < b ? a : b;
}

main(){
	cin >> n >> s;
	s = ' ' + s;
	
	for (int i = 1; i <= n; i++) {
		
		if (s[i] == 'R') {
			cnt[0]++;
			in[0][cnt[0]] = i;
		}
		else if (s[i] == 'G') {
			cnt[1]++;
			in[1][cnt[1]] = i;
		}
		else {
			cnt[2]++;
			in[2][cnt[2]] = i;
		}
	}
	for (int i = 1; i <= cnt[0]; i++) {
		for (int j = 1; j <= cnt[1]; j++) {
			if ( in[1][j] > in[0][i] )
				cn[0][0][i][j] = cn[0][0][i][j - 1] + 1;	
		}
		for (int j = 1; j <= cnt[2]; j++) {
			if ( in[2][j] > in[0][i] )
				cn[0][1][i][j] = cn[0][1][i][j - 1] + 1;
		}
	}
	for (int i = 1; i <= cnt[1]; i++) {
		for (int j = 1; j <= cnt[0]; j++) {
			if ( in[0][j] > in[1][i] )
				cn[1][0][i][j] = cn[1][0][i][j - 1] + 1;	
		}
		for (int j = 1; j <= cnt[2]; j++) {
			if ( in[2][j] > in[1][i] )
				cn[1][1][i][j] = cn[1][1][i][j - 1] + 1;
		}
	}
	for (int i = 1; i <= cnt[2]; i++) {
		for (int j = 1; j <= cnt[1]; j++) {
			if ( in[1][j] > in[2][i] )
				cn[2][0][i][j] = cn[2][0][i][j - 1] + 1;	
		}
		for (int j = 1; j <= cnt[0]; j++) {
			if ( in[0][j] > in[2][i] )
				cn[2][1][i][j] = cn[2][1][i][j - 1] + 1;
		}
	}
	for (int i = 0; i <= cnt[0]; i++)
		for (int j = 0; j <= cnt[1]; j++)
			for (int k = 0; k <= cnt[2]; k++)
				for (int last = 0; last < 3; last++)
					dp[i][j][k][last] = 1e9 + 7;
					
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	
	for (int i = 0; i <= cnt[0]; i++) {
		for (int j = 0; j <= cnt[1]; j++) {
			for (int k = 0; k <= cnt[2]; k++) {
				for (int last = 0; last < 3; last++) {
					
					if (i + 1 <= cnt[0] && last != 0)
						dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[0][i + 1] + cn[0][0][i + 1][j] + cn[0][1][i + 1][k]) ) );
					
					if (j + 1 <= cnt[1] && last != 1)
						dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[1][j + 1] + cn[1][0][j + 1][i] + cn[1][1][j + 1][k]) ) );
					
					if (k + 1 <= cnt[2] && last != 2){
						dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[2][k + 1] + cn[2][0][k + 1][j] + cn[2][1][k + 1][i]) ) );
					}
				}
			}
		}
	}
	if ( min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) > 1e9 )
		cout << -1 << endl;
	else
		cout << min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) << endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25