제출 #1266407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266407		witek_cpp	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	261 ms	135524 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())

const int DUZO = 1'000'000;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	f(i, 0, n) {
		char p1;
		cin >> p1;
		if (p1 == 'R') a[i] = 0;
		else if (p1 == 'Y') a[i] = 1;
		else a[i] = 2;
	}
	vector<vector<int>> wstp = {{-1}, {-1}, {-1}};
	f(i, 0, n) wstp[a[i]].pb(i);
	if ((max(sz(wstp[0]), max(sz(wstp[1]), sz(wstp[2]))) - 1) > (n + 1)/2) {
		cout << -1;
		return 0;
	}
	vector<vector<vector<int>>> ile(3); //ile[a][b][c] - ile z b pierwszych elementow z grupy a jest wieksze niz c;
	f(i, 0, 3) {
		ile[i].resize(sz(wstp[i]) + 1, vector<int>(n));
	}
	f(i, 0, 3) ile[i][0][0] = 0;
	f(grupa, 0, 3) {
		f(pref, 1, sz(wstp[grupa])) {
			f(val, 0, n) {
				ile[grupa][pref][val] = ile[grupa][pref - 1][val];
				if (wstp[grupa][pref] > val) ile[grupa][pref][val]++;
			}
		}
	}
	
	vector<vector<vector<vector<int>>>> dp(sz(wstp[0]), vector<vector<vector<int>>>(sz(wstp[1]), vector<vector<int>>(sz(wstp[2]), vector<int>(3)))); //dp[a][b][c][d] - jaki jest wynik dla odpowiednich prefikosw wst - d to ostatni element
	
	f(i, 0, 3) dp[0][0][0][i] = 0;
	
	f(a, 0, sz(wstp[0])) {
		f(b, 0, sz(wstp[1])) {
			f(c, 0, sz(wstp[2])) {
				if (a == b && b == c && c == 0) continue;
				f(ost, 0, 3) {
					vector<int> ile_aktl_wstp = {a, b, c};
					if (ile_aktl_wstp[ost] == 0 || (((ile_aktl_wstp[0] + ile_aktl_wstp[1] + ile_aktl_wstp[2]) + 1)/2) < max(ile_aktl_wstp[0], max(ile_aktl_wstp[1], ile_aktl_wstp[2]))) {
						dp[a][b][c][ost] = DUZO;
						continue;
					} 
					int koszt = wstp[ost][ile_aktl_wstp[ost]];
					f(i, 0, 3) {
						if (i == ost) continue;
						koszt += ile[i][ile_aktl_wstp[i]][wstp[ost][ile_aktl_wstp[ost]]];
					}
					koszt -= (a + b + c - 1);
					if (ost == 0) {
						dp[a][b][c][ost] = min(dp[a - 1][b][c][1], dp[a - 1][b][c][2]);
					} else if (ost == 1) {
						dp[a][b][c][ost] = min(dp[a][b - 1][c][0], dp[a][b - 1][c][2]);
					} else {
						dp[a][b][c][ost] = min(dp[a][b][c - 1][0], dp[a][b][c - 1][1]);
					}
					dp[a][b][c][ost] += koszt;
				}
			}
		}
	}
	int wnk = DUZO;
	f(i, 0, 3) {
		wnk = min(wnk, dp[sz(wstp[0]) - 1][sz(wstp[1]) - 1][sz(wstp[2]) - 1][i]);
	}
	cout << wnk;
	/*f(a, 0, sz(wstp[0])) {
		f(b, 0, sz(wstp[1])) {
			f(c, 0, sz(wstp[2])) {
				f(ost, 0, 3) {
					cout << "dp[" << a << "][" << b << "][" << c << "][" << ost << "] = " << dp[a][b][c][ost] << "\n";
				}
			}
		}
	}*/
	return 0;
}

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