제출 #363428

#제출 시각아이디문제언어결과실행 시간메모리
363428ijxjdjdGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
51 ms28780 KiB
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 400;
//int dp[MAXN][MAXN][MAXN][3];
int plc[3][MAXN];
int ft[MAXN][3];
int cnt[3];
int INF = (int)(1e8);
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	FR(i, N) {
	    char a;
	    cin >> a;
	    int d = (a == 'R' ? 0 : (a == 'G' ? 1 : 2));
        cnt[d]++;
        plc[d][cnt[d]] = i;
        copy(all(cnt), begin(ft[i]));
	}
	int dp[cnt[0]+1][cnt[1]+1][cnt[2]+1][3];
	fill(all(dp[0][0][0]), 0);
    for (int i = 0; i <= cnt[0]; i++) {
        for (int j = 0; j <= cnt[1]; j++) {
            for (int k = 0; k <= cnt[2]; k++) {
                for (int z = 0; z <= 2; z++) {
                    if (i == 0 && j == 0 && k == 0) {
                        dp[i][j][k][z] = 0;
                    }
                    else {
                        dp[i][j][k][z] = INF;
                        if (z == 0) {
                            if (i != 0) {
                                dp[i][j][k][z] = min(dp[i-1][j][k][1], dp[i-1][j][k][2]) + max(0, ft[plc[0][i]][1] - j) + max(0, ft[plc[0][i]][2] - k);
                            }
                        }
                        else if (z == 1) {
                            if (j != 0) {
                                dp[i][j][k][z] = min(dp[i][j-1][k][0], dp[i][j-1][k][2]) + max(0, ft[plc[1][j]][0] - i) + max(0, ft[plc[1][j]][2] - k);
                            }
                        }
                        else {
                            if (k != 0) {
                                dp[i][j][k][z] = min(dp[i][j][k-1][0], dp[i][j][k-1][1]) + max(0, ft[plc[2][k]][0] - i) + max(0, ft[plc[2][k]][1] - j);
                            }
                        }
//                        cout << i << " " << j << " " << k << " " << z << ": " <<dp[i][j][k][z] << '\n';
                    }
                }
            }
        }
    }
    cout << (*min_element(all(dp[cnt[0]][cnt[1]][cnt[2]])) >= INF ? -1 : *min_element(all(dp[cnt[0]][cnt[1]][cnt[2]]))) << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...