Submission #920415

#	Time	Username	Problem	Language	Result	Execution time	Memory
920415		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	268 ms	134992 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using i64 = long long;
#define all(x) (x).begin(), (x).end()

const int N = 400 + 5;
const int INF = 1E9;

int n, pre[3][N][3];
std::vector<int> idxs[3];
std::vector<std::vector<std::vector<std::vector<int>>>> dp;

std::vector<int>::iterator it;

int f(int a, int b, int c, int last) {
	if(dp[a][b][c][last] != -1) {
		return dp[a][b][c][last];
	} else if(a + b + c == n) {
		return 0;
	}

	int res = INF;
	if(a != idxs[0].size() && last != 0) {
		int cost = 0;
		cost += std::max(0, pre[0][a][1] - b);
		cost += std::max(0, pre[0][a][2] - c);

		res = std::min(res, f(a + 1, b, c, 0) + cost);
	}

	if(b != idxs[1].size() && last != 1) {
		int cost = 0;
		cost += std::max(0, pre[1][b][0] - a);
		cost += std::max(0, pre[1][b][2] - c);

		res = std::min(res, f(a, b + 1, c, 1) + cost);
	}

	if(c != idxs[2].size() && last != 2) {
		int cost = 0;
		cost += std::max(0, pre[2][c][0] - a);
		cost += std::max(0, pre[2][c][1] - b);

		res = std::min(res, f(a, b, c + 1, 2) + cost);
	}

	return dp[a][b][c][last] = res;
}

void solve() {
	std::string s;
	std::cin >> n >> s;

	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') {
			idxs[0].emplace_back(i);
		} else if(s[i] == 'G') {
			idxs[1].emplace_back(i);
		} else {
			idxs[2].emplace_back(i);
		}
	}

	dp.assign(idxs[0].size() + 1, std::vector (idxs[1].size() + 1, std::vector (idxs[2].size() + 1, std::vector (4, -1))));

	for(int i = 0; i < idxs[0].size(); i++) {
		pre[0][i][1] = std::upper_bound(all(idxs[1]), idxs[0][i]) - idxs[1].begin();
		pre[0][i][2] = std::upper_bound(all(idxs[2]), idxs[0][i]) - idxs[2].begin();
	}

	for(int i = 0; i < idxs[1].size(); i++) {
		pre[1][i][0] = std::upper_bound(all(idxs[0]), idxs[1][i]) - idxs[0].begin();
		pre[1][i][2] = std::upper_bound(all(idxs[2]), idxs[1][i]) - idxs[2].begin();
	}

	for(int i = 0; i < idxs[2].size(); i++) {
		pre[2][i][0] = std::upper_bound(all(idxs[0]), idxs[2][i]) - idxs[0].begin();
		pre[2][i][1] = std::upper_bound(all(idxs[1]), idxs[2][i]) - idxs[1].begin();
	}

	int ans = f(0, 0, 0, 3);
	if(ans != INF) {
		std::cout << ans;
	} else {
		std::cout << -1;
	}

	return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:22:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if(a != idxs[0].size() && last != 0) {
      |     ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:30:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  if(b != idxs[1].size() && last != 1) {
      |     ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  if(c != idxs[2].size() && last != 2) {
      |     ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < idxs[0].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < idxs[1].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i = 0; i < idxs[2].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

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