Submission #1172504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172504		pinbu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	169 ms	141016 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

const int N = 404;
void mini(int &X, int Y) {
	if (X > Y) X = Y;
}

int n;
string s;
vector<int> pos[3] {{-1}, {-1}, {-1}}, num[3][N];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> s;
    s = '&' + s;
    for (int i = 1; i <= n; i++) {
    	pos[(s[i] < 'R') + (s[i] < 'Y')].emplace_back(i);
    }
    int ng = pos[0].size() - 1, nr = pos[1].size() - 1, ny = pos[2].size() - 1;
    vector<vector<vector<vector<int>>>> dp(ng + 3, vector<vector<vector<int>>>(nr + 3, vector<vector<int>>(ny + 3, vector<int>(3, N * N))));
	for (int i = 0; i <= n; i++) {
		num[0][i].resize(ng + 3, 0);
		num[1][i].resize(nr + 3, 0);
		num[2][i].resize(ny + 3, 0);
	}
	
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 1; i <= n; i++) {
    	for (int x = 1; x <= ng; x++) {
	    	num[0][i][x] = num[0][i][x - 1] + (pos[0][x] <= i);
	    }
	    for (int y = 1; y <= nr; y++) {
	    	num[1][i][y] = num[1][i][y - 1] + (pos[1][y] <= i);
	    }
	    for (int z = 1; z <= ny; z++) {
	    	num[2][i][z] = num[2][i][z - 1] + (pos[2][z] <= i);
	    }
    }
    auto shift = [&] (int x, int y, int z, int p) {
    	return x - num[0][p][x] + y - num[1][p][y] + z - num[2][p][z];
    };
    for (int x = 0; x <= ng; x++) {
    	for (int y = 0; y <= nr; y++) {
    		for (int z = 0; z <= ny; z++) {
    			int i = x + y + z;
    			if (x) {
    				mini(dp[x][y][z][0], min(dp[x - 1][y][z][1], dp[x - 1][y][z][2]) + pos[0][x] + shift(x, y, z, pos[0][x]) - i);
    			}
    			if (y) {
    				mini(dp[x][y][z][1], min(dp[x][y - 1][z][2], dp[x][y - 1][z][0]) + pos[1][y] + shift(x, y, z, pos[1][y]) - i);
    			}
    			if (z) {
    				mini(dp[x][y][z][2], min(dp[x][y][z - 1][0], dp[x][y][z - 1][1]) + pos[2][z] + shift(x, y, z, pos[2][z]) - i);
    			}
    		}
    	}
    }
    int res = min({dp[ng][nr][ny][0], dp[ng][nr][ny][1], dp[ng][nr][ny][2]});
    cout << (res >= N * N ? -1 : res);
    
    return 0;
}

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