Submission #936675

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

joi2019_ho_t3

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define inf ((int)1e6)
using namespace std;
const int N = 403;
int dp[N][N][N][3];
int bs[3][3][N];

int32_t main(){
	fast
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt[3] = {0, 0, 0};
	vector <vector<int> > pos(3);
	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') {
			cnt[0]++;
			pos[0].push_back(i);
		}
		else if(s[i] == 'G') {
			cnt[1]++;
			pos[1].push_back(i);
		}
		else {
			cnt[2]++;
			pos[2].push_back(i);
		}
	}
	pos[0].push_back(inf);
	pos[1].push_back(inf);
	pos[2].push_back(inf);
	for(int r = 0; r <= cnt[0]; r++)
		for(int g = 0; g <= cnt[1]; g++)
			for(int y = 0; y <= cnt[2]; y++)
				for(int last = 0; last < 3; last++)
					dp[r][g][y][last] = inf;
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < pos[i].size(); k++) {
				bs[i][j][k] = lower_bound(pos[j].begin(), pos[j].end(), pos[i][k]) - pos[j].begin();
			}
		}
	}

	dp[1][0][0][0] = pos[0][0];
	dp[0][1][0][1] = pos[1][0];
	dp[0][0][1][2] = pos[2][0];
	auto adjust = [&](int x, int y, int z) {
		int ix = pos[0][x];
		ix += max(0, y - bs[0][1][x]);
		ix += max(0, z - bs[0][2][x]);
		//cout << bs[0][1][x] << " " << bs[0][2][x] << "\n";
		int iy = pos[1][y];
		iy += max(0, x - bs[1][0][y]);
		iy += max(0, z - bs[1][2][y]);
		int iz = pos[2][z];
		iz += max(0, x - bs[2][0][z]);
		iz += max(0, y - bs[2][1][z]);
		return array<int, 3>{ix, iy, iz};
	};
	auto a = adjust(0, 0, 0);
	//cout << a[0] << " " << a[1] << " " << a[2] << "\n";
	for(int r = 0; r <= cnt[0]; r++) {
		for(int g = 0; g <= cnt[1]; g++) {
			for(int y = 0; y <= cnt[2]; y++) {
				auto [ir, ig, iy] = adjust(r, g, y);
				int ind = r + g + y;
				for(int last : {0, 1, 2}) {
					int val = dp[r][g][y][last];
					// cout << r << " " << g << " " << y << " " << last << "\n";
					// cout << ir << " " << ig << " " << iy << " " << ind << "\n";
					// cout << val << "\n";
					if(val >= inf) continue;
					if(last != 0) {
						dp[r+1][g][y][0] = min(dp[r+1][g][y][0], val + abs(ir - ind));
					}
					if(last != 1) {
						dp[r][g+1][y][1] = min(dp[r][g+1][y][1], val + abs(ig - ind));
					}
					if(last != 2) {
						dp[r][g][y+1][2] = min(dp[r][g][y+1][2], val + abs(iy - ind));
					}
				}
			}
		}
	}
	int ans = inf;
	for(int i = 0; i < 3; i++) {
		ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
	}
	if(ans == inf) cout << -1;
	else cout << ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int k = 0; k < pos[i].size(); k++) {
      |                   ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:63:7: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   63 |  auto a = adjust(0, 0, 0);
      |       ^

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