제출 #116795

#제출 시각아이디문제언어결과실행 시간메모리
116795ZwariowanyMarcinGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
5 / 100
118 ms163072 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define ld long double #define fi first #define se second #define ll long long #define ss(x) (int) x.size() #define mp make_pair #define FOR(i, n) for(int i = 1; n >= i; ++i) using namespace std; using namespace __gnu_pbds; const int inf = 1e9 + 1; int dp[405][405][405][3]; int n; string s; int cnt[405][3]; int t[405]; vector <int> v[3]; int ile[3]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> s; for(int i = 0; i < n; ++i) { if(s[i] == 'R') t[i + 1] = 0; if(s[i] == 'G') t[i + 1] = 1; if(s[i] == 'Y') t[i + 1] = 2; } for(int i = 0; i < 3; ++i) { v[i].pb(0); } for(int i = 1; i <= n; ++i) { for(int j = 0; j < 3; ++j) cnt[i][j] = cnt[i - 1][j]; cnt[i][t[i]]++; v[t[i]].pb(i); } int R = cnt[n][0]; int G = cnt[n][1]; int Y = cnt[n][2]; for(int r = 0; r <= R; ++r) for(int g = 0; g <= G; ++g) for(int y = 0; y <= Y; ++y) for(int z = 0; z < 3; ++z) dp[r][g][y][z] = inf; dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0; int maxi = max({R, G, Y}); if(maxi > n / 2 + 1) { cout << -1; return 0; } for(int r = 0; r <= R; ++r) for(int g = 0; g <= G; ++g) for(int y = 0; y <= Y; ++y) { for(int last = 0; last < 3; ++last) { int ans = dp[r][g][y][last]; ile[0] = r; ile[1] = g; ile[2] = y; for(int i = 0; i < 3; ++i) { if(i == last || ile[i] + 1 == ss(v[i])) continue; int pos = v[i][ile[i] + 1]; int add = -1 + pos - r - g - y; for(int j = 0; j < 3; ++j) { int ost = v[j][ile[j]]; add += max(0, cnt[ost][j] - cnt[pos][j]); } //cout << r << " " << g << " " << y << " " << " " << i << " " << ans << endl; ile[i]++; dp[ile[0]][ile[1]][ile[2]][i] = min(dp[ile[0]][ile[1]][ile[2]][i], add + ans); ile[i]--; } } } int best = inf; for(int i = 0; i < 3; ++i) best = min(best, dp[R][G][Y][i]); cout << best; 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...