Submission #136819

#	Time	Username	Problem	Language	Result	Execution time	Memory
136819		ekrem	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++98	0 / 100	907 ms	1048580 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 4005

using namespace std;

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

int n, a[N], dp[N][N][5][5];
map < char , int > h;

int f(int bas, int son, int d1, int d2){
	if(bas == son)
		return (a[bas] != d1 and a[bas] != d2)?0:inf;
	if(bas > son)
		return (d1 != d2)?0:inf;

	int &r = dp[bas][son][d1][d2];
	if(r != -1)
		return r;
	r = inf;
	if(a[bas] != d1)
		r = min(r, f(bas + 1, son, a[bas], d2));
	if(a[son] != d2)
		r = min(r, f(bas, son - 1, d1, a[son]));
	// if(a[son] != d1 and a[bas] != d2)
	// 	r = min(r, f(bas + 1, son - 1, a[son], a[bas]) + 1);
	for(int i = bas + 1; i <= son; i++)
		// if(a[i] != d1)
			r = min(r, f(bas, i - 1, a[i], a[i + 1]) + f(i + 1, son, a[i - 1], d2) + i - bas);
	for(int i = bas; i < son; i++)
		// if(a[i] != d2)
			r = min(r, f(bas, i - 1, d1, a[i + 1]) + f(i + 1, son, a[i - 1], a[i]) + son - i);
	// cout << bas << " " << son << " " << d1 << " " << d2 << " -> " << r << endl;
	return r;
}

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];	
	}
	// for(int i = 1; i <= n; i++)cout << a[i] << " ";cout << endl;
	if(f(1, n, 0, 0) >= inf)
		printf("-1\n");
	else
		printf("%d\n", f(1, n, 0, 0));
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:56: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&x);
   ~~~~~^~~~~~~~~~

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