제출 #1180821

#제출 시각아이디문제언어결과실행 시간메모리
1180821miniobGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
75 ms163856 KiB
#include <bits/stdc++.h> using namespace std; int dp[407][407][407][4]; int pom[3][407][407]; vector<int> pos[3]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; string s; cin >> n >> s; for (int i = 0; i < n; i++) { if(s[i] == 'R') { pos[0].push_back(i); } else if(s[i] == 'G') { pos[1].push_back(i); } else if(s[i] == 'Y') { pos[2].push_back(i); } } for (int i = 0; i < 3; i++) { if (pos[i].size() > (n + 1) / 2) { cout << -1 << endl; return 0; } } for (int i = 0; i < 3; i++) { for (int j = 0; j <= pos[i].size(); j++) { for (int k = 0; k <= n; k++) { if(j == 0) { pom[i][j][k] = 0; } else { pom[i][j][k] = pom[i][j - 1][k]; if(k > pos[i][j - 1]) { pom[i][j][k]++; } } } } } for (int i = 0; i <= pos[0].size(); i++) { for (int j = 0; j <= pos[1].size(); j++) { for (int k = 0; k <= pos[2].size(); k++) { for (int l = 0; l < 4; l++) { dp[i][j][k][l] = 8000000; } } } } dp[0][0][0][3] = 0; for(int i = 0; i <= pos[0].size(); i++) { for(int j = 0; j <= pos[1].size(); j++) { for(int k = 0; k <= pos[2].size(); k++) { for(int pop = 0; pop < 4; pop++) { if(dp[i][j][k][pop] == 8000000) { continue; } for (int c = 0; c < 3; c++) { if(pop != 3 && c == pop) { continue; } if(c == 0 && i < pos[0].size()) { dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][pop] + pos[0][i] - (pom[0][i][pos[0][i]] + pom[1][j][pos[0][i]] + pom[2][k][pos[0][i]])); } if(c == 1 && j < pos[1].size()) { dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][pop] + pos[1][j] - (pom[0][i][pos[1][j]] + pom[1][j][pos[1][j]] + pom[2][k][pos[1][j]])); } if(c == 2 && k < pos[2].size()) { dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][pop] + pos[2][k] - (pom[0][i][pos[2][k]] + pom[1][j][pos[2][k]] + pom[2][k][pos[2][k]])); } } } } } } int odp = 8000000; for (int i = 0; i < 3; i++) { odp = min(odp, dp[pos[0].size()][pos[1].size()][pos[2].size()][i]); } if(odp == 8000000) { cout << -1 << endl; } else { cout << odp << endl; } 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...