제출 #1107372

#제출 시각아이디문제언어결과실행 시간메모리
1107372vjudge1Growing Vegetable is Fun 3 (JOI19_ho_t3)C++17
75 / 100
506 ms774808 KiB
# include <bits/stdc++.h> // #pragma optimize("g", on) // #pragma GCC optimize ("inline") // #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC optimize ("03") // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native") #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; # define ll long long # define pii pair <int, int> # define pll pair <ll, ll> # define nl '\n' # define sz(x) (int)(x).size() # define all(x) (x).begin(), (x).end() # define deb(x) cerr << #x << " = " << x << endl; const int maxn = (int)404; const ll inf = (ll)1e9 + 0; const int mod = (int)1e9 + 7; const bool T = 0; int n; string s; int dp[maxn][maxn][maxn][3]; int pref[3][maxn]; vector <int> g[3]; int d[3]; int f (char c) { if (c == 'R') return 0; if (c == 'G') return 1; if (c == 'Y') return 2; assert(0); return -1; } void op (int &a, int b) { a = min(a, b); } void ma1n () { cin >> n >> s; g[0].push_back(0); g[1].push_back(0); g[2].push_back(0); for (int i = 0; i < n; ++i) { for (int j = 0; j < 3; ++j) { pref[j][i + 1] = pref[j][i]; } int x = f(s[i]); pref[x][i + 1]++; g[x].push_back(i + 1); } memset(dp, 0x3f, sizeof dp); int lim = dp[3][2][1][0]; dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; // deb(s); // exit(0); for (int i = 0; i < n; ++i) { for (int x = 0; x <= min(i, pref[0][n]); ++x) { for (int y = 0; y <= min(i - x, pref[1][n]); ++y) { if (x + y > i) continue; int z = i - x - y; if (z > pref[2][n]) continue; d[0] = x, d[1] = y, d[2] = z; for (int prv = 0; prv < 3; ++prv) { for (int cur = 0; cur < 3; ++cur) { if (prv == cur || d[cur] == pref[cur][n]) continue; // cout << "continue everything" << nl; // continue; int othr = prv ^ cur ^ 3; assert(othr >= 0 && othr < 3 && othr != prv && othr != cur); int id = g[cur][d[cur] + 1]; op(dp[i + 1][x + (cur == 0)][y + (cur == 1)][cur], dp[i][x][y][prv] + max(pref[prv][id] - d[prv], 0) + max(pref[othr][id] - d[othr], 0)); } } } } } int ans = lim; for (int last = 0; last < 3; ++last) { ans = min(ans, dp[n][pref[0][n]][pref[1][n]][last]); // cout << pref[0][n] << ' ' << pref[1][n] << ' ' << last << ' ' <<dp[n][pref[0][n]][pref[1][n]][last] << nl; } // for (int x = 0; x <= n; ++x) { // for (int y = 0; y <= n; ++y) { // if (x + y > n) continue; // for (int last = 0; last < 3; ++last) { // ans = min(ans, dp[n][x][y][last]); // if (dp[n][x][y][last] != lim) { // cout << x << ' ' << y << ' ' << last << ' ' << dp[n][x][y][last] << nl; // } // } // } // } cout << (ans == lim ? -1 : ans) << nl; } signed main () { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ttt = 1; if (T) cin >> ttt; while (ttt--) { ma1n(); } 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...