Submission #136909

#	Time	Username	Problem	Language	Result	Execution time	Memory
136909		ekrem	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++98	100 / 100	268 ms	169208 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define mod 1000000007
#define inf 1000000009
#define N 410

using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, ans, a[N], say[5], dp[N/2][N/2][N/2][5], pre[N][5], yer[5][N];
map < char , int > h;

int f(int r, int g, int y, int lst){
	if(r < 0 or g < 0 or y < 0)
		return inf;
	if(r + g + y == 0)
		return 0;
	int &ans = dp[r][g][y][lst];
	if(ans != -1)
		return ans;
	ans = inf;
	if(lst == 1){//r yapcan
		int ind = yer[1][r];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r - 1, g, y, 2) + of);
		ans = min(ans, f(r - 1, g, y, 3) + of);
	}
	if(lst == 2){//g yapcan
		int ind = yer[2][g];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r, g - 1, y, 1) + of);
		ans = min(ans, f(r, g - 1, y, 3) + of);
		// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
	}
	if(lst == 3){//y yapcan
		int ind = yer[3][y];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r, g, y - 1, 1) + of);
		ans = min(ans, f(r, g, y - 1, 2) + of);
		// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
	}
	// cout << r << " " << g << " " << y << " " << lst << " = " <<  ans << endl;
	return ans;
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	h['R'] = 1;
	h['G'] = 2;
	h['Y'] = 3;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		char x;
		scanf(" %c",&x);
		a[i] = h[x];	
		say[a[i]]++;
		yer[a[i]][say[a[i]]] = i;
		for(int j = 1; j <= 3; j++)
			pre[i][j] = pre[i - 1][j] + (a[i] == j);
	}
	if(max(max(say[2], say[3]),say[1]) > n/2 + 3 ){
		printf("-1\n");
		return 0;
	}
	ans = min(min(f(say[1], say[2], say[3], 1), f(say[1], say[2], say[3], 2)), f(say[1], say[2], say[3], 3));
	if(ans >= inf)
		printf("-1\n");
	else
		printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&x);
   ~~~~~^~~~~~~~~~

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