Submission #234964

#TimeUsernameProblemLanguageResultExecution timeMemory
234964davitmargGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
60 / 100
1147 ms760952 KiB
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; const int N = 402; int pr[3][N], n, dp[N][N][N][3]; vector<int> pos[3]; string s; int ind(char x) { if (x == 'R') return 0; if (x == 'G') return 1; return 2; } int get(int i, int l, int r) { return max(0, pr[i][r] - pr[i][l - 1]); } int calc(int x,int a, int b, int c) { a++; b++; c++; int p; if (x == 0) p = a; else if (x == 1) p = b; else p = c; int res = 0; if (p > pos[x].size()) return mod; if (x != 0 && a <= pos[0].size()) res += get(0, pos[0][a - 1], pos[x][p - 1]); if (x != 1 && b <= pos[1].size()) res += get(1, pos[1][b - 1], pos[x][p - 1]); if (x != 2 && c <= pos[2].size()) res += get(2, pos[2][c - 1], pos[x][p - 1]); return res; } int main() { fastIO; cin >> n; cin >> s; s = "#" + s; for (int i = 1; i <= n; i++) { for (int j = 0; j < 3; j++) pr[j][i] = pr[j][i - 1]; pr[ind(s[i])][i]++; pos[ind(s[i])].push_back(i); } for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = mod; dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; for (int k = 0; k < n; k++) for (int a = 0; a <= k && a <= pos[0].size(); a++) for (int b = 0; a + b <= k && b <= pos[1].size(); b++) { int c = k - a - b; for (int j = 0; j < 3; j++) { int val = calc(j, a, b, c); for (int i = 0; i < 3; i++) { if (i == j) continue; dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j] = min(dp[a][b][c][i] + val, dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j]); } } } int ans = min(dp[pr[0][n]][pr[1][n]][pr[2][n]][0], min(dp[pr[0][n]][pr[1][n]][pr[2][n]][1], dp[pr[0][n]][pr[1][n]][pr[2][n]][2])); if (ans == mod) ans = -1; cout << ans << endl; return 0; } /* */

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int calc(int, int, int, int)':
joi2019_ho_t3.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (p > pos[x].size())
      ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 0 && a <= pos[0].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 1 && b <= pos[1].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 2 && c <= pos[2].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:96:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int a = 0; a <= k && a <= pos[0].size(); a++)
                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:97:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
                                  ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...