Submission #1089422

#TimeUsernameProblemLanguageResultExecution timeMemory
1089422vjudge1Growing Vegetable is Fun 3 (JOI19_ho_t3)C++17
15 / 100
2 ms2140 KiB
#include <bits/stdc++.h> #define int long long #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define sz size() #define yes "YES" #define no "NO" #define IOI ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pf push_front #define pb push_back #define S second #define F first using namespace std; const int N = 400 + 1; const int NN = 1e5; const int mod = (1e9 + 7); const int inf = 1e18; int n, pref[3][N]; vector<int> g[3]; string s; void legenda_ne_umret() { cin >> n >> s; s = '+' + s; for (int i = 1; i <= n; i++) { if (s[i] == 'Y') { g[0].pb(i); } if (s[i] == 'R') { g[1].pb(i); } if (s[i] == 'G') { g[2].pb(i); } pref[0][i] = pref[0][i - 1] + (s[i] == 'Y'); pref[1][i] = pref[1][i - 1] + (s[i] == 'R'); pref[2][i] = pref[2][i - 1] + (s[i] == 'G'); } int allr = pref[1][n]; int ally = pref[0][n]; int allg = pref[2][n]; int dp[n + 1][allr + 1][ally + 1][3]; for (int id = 1; id <= n; id++) { for (int a = 0; a <= allr; a++) { for (int b = 0; b <= ally; b++) { dp[id][a][b][0] = inf; dp[id][a][b][1] = inf; dp[id][a][b][2] = inf; } } } dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; for (int id = 1; id <= n; id++) { for (int a = 0; a <= allr ; a++) { for (int b = 0; b <= ally; b++) { int c = id - a - b; if(c>allg || a + b > id)continue; if (a > 0) { int pos = g[1][a - 1]; int cnt = max(0ll , b - pref[0][pos]) + max(0ll , c - pref[2][pos]); dp[id][a][b][0] = min(dp[id - 1][a - 1][b][1], dp[id - 1][a - 1][b][2]) + max(0ll, (pos + cnt) - id); } if (b > 0) { int pos = g[0][b - 1]; int cnt = max(0ll , a - pref[1][pos]) + max(0ll , c - pref[2][pos]); dp[id][a][b][1] = min(dp[id - 1][a][b - 1][0], dp[id - 1][a][b - 1][2]) + max(0ll, (pos + cnt) - id); } if (c > 0) { int pos = g[2][c - 1]; int cnt = max(0ll , b - pref[0][pos]) + max(0ll , a - pref[1][pos]); dp[id][a][b][2] = min(dp[id - 1][a][b][0], dp[id - 1][a][b][1]) + max(0ll, (pos + cnt) - id); } } } } cout << (min({dp[n][allr][ally][0], dp[n][allr][ally][1], dp[n][allr][ally][2]}) == inf ? -1 : min({dp[n][allr][ally][0], dp[n][allr][ally][1], dp[n][allr][ally][2]})); } signed main() { // IOI; // freopen("maze.in", "r", stdin); // freopen("maze.out", "w", stdout); ///////////////////////////////////////////// int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { // cout << "Case " << i << ":\n"; legenda_ne_umret(); cout << '\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...