Submission #538098

#	Time	Username	Problem	Language	Result	Execution time	Memory
538098		pavement	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	214 ms	164808 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, cnt[3], tmp[3][405][3], dp[405][405][405][3];
char S[405];
vector<int> vec[3];

int cst(int a, int x, int b, int y) {
	return max(0ll, y - tmp[a][x][b]);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> S[i];
		if (S[i] == 'R') S[i] = 0;
		else if (S[i] == 'G') S[i] = 1;
		else S[i] = 2;
		cnt[S[i]]++;
		vec[S[i]].pb(i);
	}
	for (int a = 0; a < 3; a++)
		for (int x = 1; x <= cnt[a]; x++)
			for (int b = 0; b < 3; b++)
				if (a != b) tmp[a][x][b] = lower_bound(vec[b].begin(), vec[b].end(), vec[a][x - 1]) - vec[b].begin();
	for (int sum = cnt[0] + cnt[1] + cnt[2]; sum >= 0; sum--) {
		for (int i = 0; i <= cnt[0]; i++)
			for (int j = max(0ll, sum - i - cnt[2]); j <= min(sum - i, cnt[1]); j++) {
				int k = sum - i - j;
				for (int p = 0; p < 3; p++) {
					if (i + j + k == cnt[0] + cnt[1] + cnt[2]) {
						dp[i][j][k][p] = 0;
						continue;
					}
					dp[i][j][k][p] = 1e16;
					if (i < cnt[0] && p != 0) dp[i][j][k][p] = min(dp[i][j][k][p], dp[i + 1][j][k][0] + cst(0, i + 1, 1, j) + cst(0, i + 1, 2, k));
					if (j < cnt[1] && p != 1) dp[i][j][k][p] = min(dp[i][j][k][p], dp[i][j + 1][k][1] + cst(1, j + 1, 0, i) + cst(1, j + 1, 2, k));
					if (k < cnt[2] && p != 2) dp[i][j][k][p] = min(dp[i][j][k][p], dp[i][j][k + 1][2] + cst(2, k + 1, 0, i) + cst(2, k + 1, 1, j));
				}
			}
	}
	int r = min({dp[0][0][0][0], dp[0][0][0][1], dp[0][0][0][2]});
	if (r >= (int)1e15) cout << "-1\n";
	else cout << r << '\n';
}

Compilation message (stderr)

joi2019_ho_t3.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main() {
      | ^~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:46:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |   cnt[S[i]]++;
      |       ~~~^
joi2019_ho_t3.cpp:47:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |   vec[S[i]].pb(i);
      |       ~~~^

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