Submission #316762

#	Time	Username	Problem	Language	Result	Execution time	Memory
316762		aZvezda	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1088 ms	15872 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 810, offset = 410;
int dp[2][MAX_N][MAX_N][3];
int n;
string in;

int getCode(char c) {
	if(c == 'R') {
		return 0;
	} else if(c == 'G') {
		return 1;
	} else if(c == 'Y') {
		return 2;
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for(int i = 0; i < 2; i ++) {
		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int q = 0; q < 3; q ++) {
					dp[i][j][k][q] = mod;
				}
			}
		}
	} 
	cin >> n;
	cin >> in;
	dp[0][offset][offset][0] = 0;
	dp[0][offset][offset][1] = 0;
	dp[0][offset][offset][2] = 0;
	for(int i = 0; i < n; i ++) { 
		int curr = i & 1, nxt = curr ^ 1;
		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int last = 0; last < 3; last ++) {
					dp[nxt][j][k][last] = mod;
				}
			}
		}

		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int last = 0; last < 3; last ++) {
					if(dp[curr][j][k][last] == mod) {continue;}
					int cnt[3] = {j - offset, k - offset, 0};
					cnt[2] = 0 - cnt[0] - cnt[1];
					cnt[getCode(in[i])] ++;
					for(int toGet = 0; toGet < 3; toGet ++) {
						if(toGet == last) {continue;}
						cnt[toGet] --;
						chkmin(dp[nxt][cnt[0] + offset][cnt[1] + offset][toGet], dp[curr][j][k][last] + abs(cnt[0]) + abs(cnt[1]) + abs(cnt[2]));
						cnt[toGet] ++;
					}
				}
			}
		}
	}
	int ans = mod;
	for(int i = 0; i < 3; i ++) {
		chkmin(ans, dp[n & 1][offset][offset][i]);
	}
	if(ans > MAX_N) {
		cout << -1 << endl;
	} else {
		cout << ans / 2 << endl;
	}
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int getCode(char)':
joi2019_ho_t3.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

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