제출 #363428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363428		ijxjdjd	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	51 ms	28780 KiB

joi2019_ho_t3

#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;
}

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