제출 #1330339

#제출 시각아이디문제언어결과실행 시간메모리
1330339blackscreen1Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
90 ms164916 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, a[405], x[3], t1, t2, t3;
string s;
ll dp[405][405][405][3];
vector<ll> v[3];
ll pf[405][3];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	pf[0][0] = pf[0][1] = pf[0][2] = 0;
	iloop(0, n) {
		jloop(0, 3) pf[i+1][j] = pf[i][j];
		if (s[i] == 'R') a[i] = 0;
		else if (s[i] == 'G') a[i] = 1;
		else a[i] = 2;
		x[a[i]]++;
		pf[i+1][a[i]]++;
		v[a[i]].push_back(i);
	}
	iloop(0, 3) if (2*x[i] - 1 > n) {cout << -1; return 0;} 
	iloop(0, x[0]+1) jloop(0, x[1]+1) kloop(0, x[2]+1) lloop(0, 3) {
		if (!(i+j+k)) {dp[i][j][k][l] = 0; continue;}
		dp[i][j][k][l] = INF;
		if (l == 0 && i == 0) continue;
		if (l == 1 && j == 0) continue;
		if (l == 2 && k == 0) continue;
		t1 = i + j + k - 1;
		if (l == 0) t3 = v[l][i-1];
		if (l == 1) t3 = v[l][j-1];
		if (l == 2) t3 = v[l][k-1];
		t2 = t3 - t1;
		if (l != 0) t2 += max(i - pf[t3][0], 0LL);
		if (l != 1) t2 += max(j - pf[t3][1], 0LL);
		if (l != 2) t2 += max(k - pf[t3][2], 0LL);
		//cout << i << "," << j << "," << k << ";" << l << ":" << t3 << " " << t2 << "\n";
		for (int _ = 0; _ < 3; _++) { // never thought id need 5
			if (_ == l) continue;
			if (l == 0) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][j][k][_] + t2);
			if (l == 1) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i][j-1][k][_] + t2);
			if (l == 2) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i][j][k-1][_] + t2);
		}
	}
	/*iloop(0, x[0]+1) jloop(0, x[1]+1) kloop(0, x[2]+1) lloop(0, 3) {
		cout << i << "," << j << "," << k << ";" << l << ":" << dp[i][j][k][l] << "\n";
	}*/
	cout << *min_element(dp[x[0]][x[1]][x[2]], dp[x[0]][x[1]][x[2]] + 3);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...