Submission #334305

#TimeUsernameProblemLanguageResultExecution timeMemory
334305HoneyBadgerGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
100 / 100
294 ms202744 KiB
#include <iostream> #include <iomanip> #include <cstdio> #include <vector> #include <bitset> #include <string> #include <cstring> #include <map> #include <set> #include <stack> #include <queue> #include <deque> #include <utility> #include <algorithm> #include <random> #include <cmath> #include <cassert> #include <climits> #include <ctime> #include <chrono> #pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #ifdef LOCAL #define dbg(x) cout << #x << " : " << x << endl; #else #define dbg(x) #endif #define pb push_back #define ppb pop_back() #define mp make_pair #define fi(a, b) for (int i = a; i < b; i++) #define fj(a, b) for (int j = a; j < b; j++) #define fk(a, b) for (int k = a; k < b; k++) #define fi1(a, b) for (int i = a - 1; i >= b; i--) #define fj1(a, b) for (int j = a - 1; j >= b; j--) #define fk1(a, b) for (int k = a - 1; k >= b; k--) #define fx(x, a) for (auto& x : a) #define rep(i, a, b) for (int i = a; i < b; ++i) #define rep1(i, a, b) for (int i = a - 1; i >= b; --i) #define siz(x) (int)x.size() #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; } template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; } ostream& operator << (ostream &out, const vector<int> &b) { for (auto k : b) out << k << ' '; return out; } typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef char ch; typedef string str; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef vector<vpii> vvpii; typedef vector<ch> vch; typedef vector<vch> vvch; typedef vector<str> vs; const int MOD = 1000000007; const int INF = 1000000050; const long long BIG = (long long)2e18 + 50; #ifdef LOCAL const int MX = 20; #else const int MX = 410; #endif const double EPS = 1e-9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; int cnt[MX][3]; int dp[MX][MX / 2][MX / 2][3]; // pref cur0 cur1 last int p[3]; int np[3]; vi in[3]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; vi a(n); fx(x, a) { char c; cin >> c; if (c == 'R') x = 0; else if (c == 'G') x = 1; else x = 2; } fi(1, n + 1) { fj(0, 3) { cnt[i][j] = cnt[i - 1][j]; } cnt[i][a[i - 1]]++; in[a[i - 1]].pb(i - 1); } fj(0, 3) { if (cnt[n][j] > (n + 1) / 2) { cout << "-1\n"; return 0; } } vi c(3); c[0] = cnt[n][0]; c[1] = cnt[n][1]; c[2] = cnt[n][2]; fi(0, MX) fj(0, MX / 2) fk(0, MX / 2) for (int l = 0; l < 3; ++l) dp[i][j][k][l] = INF; for (int l = 0; l < 3; ++l) dp[0][0][0][l] = 0; fi(0, n) { int b0 = min(c[0], i); int b1 = min(c[1], i); for (p[0] = 0; p[0] <= b0; ++p[0]) { for (p[1] = 0; p[1] <= b1; ++p[1]) { p[2] = i - p[0] - p[1]; if (p[2] < 0 || p[2] > c[2]) continue; memcpy(np, p, sizeof(p)); for (int l = 0; l < 3; ++l) { if (i && !p[l]) continue; for (int l2 = 0; l2 < 3; ++l2) { if (l2 == l || p[l2] == c[l2]) continue; np[l2]++; int j = in[l2][p[l2]]; int delta = 0; for (int col = 0; col < 3; ++col) { if (col != l2) { delta += max(0, cnt[j][col] - p[col]); } } mine(dp[i + 1][np[0]][np[1]][l2], dp[i][p[0]][p[1]][l] + delta); np[l2]--; } } } } } int ans = INF; for (int l = 0; l < 3; ++l) { mine(ans, dp[n][c[0]][c[1]][l]); } assert(ans != INF); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...