Submission #236675

#	Time	Username	Problem	Language	Result	Execution time	Memory
236675		_7_7_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	759 ms	815800 KiB

joi2019_ho_t3

#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
	
int n, cnt[N][3], dp[N][N][N][3];
vi pos[3];
string s;


int get (int l, int r, int i) {
	if (l > r)
		return 0;
	return cnt[r][i] - cnt[l - 1][i];
}

int rec (vi c, int lst) {
//	cerr << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << lst << endl;
	if (c[0] + c[1] + c[2] == 0)
		return 0;

	if (!c[lst])
		return inf;

	int &res = dp[c[0]][c[1]][c[2]][lst];
	if (res != -1)
		return res;

	c[lst]--;	
	res = inf;

	int cost = 0;
	for (int j = 0; j < 3; ++j)
		if (j != lst && c[j])
			cost += get(pos[lst][c[lst]], pos[j][c[j] - 1], j);

	for (int j = 0; j < 3; ++j)
		if (j != lst)
			res = min(res, rec(c, j) + cost);
	return res;
	
	
}
	

main () {
	cin >> n >> s;
	s = "#" + s;
	
	memset(dp, -1, sizeof(dp));

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j)
			cnt[i][j] = cnt[i - 1][j];
		if (s[i] == 'R') {
			++cnt[i][0]; 
			pos[0].pb(i);
		} else if (s[i] == 'Y') {
			++cnt[i][1]; 
			pos[1].pb(i);
		} else {
			++cnt[i][2]; 
			pos[2].pb(i);
		}
	}

	vi c;
	for (int j = 0; j < 3; ++j)
		c.pb(cnt[n][j]);

	int ans = min({rec(c, 0), rec(c, 1), rec(c, 2)});	

	if (ans == inf)
		ans = -1;

	cout << ans << endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:80:7: 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: 0 / 25