Submission #142743

#TimeUsernameProblemLanguageResultExecution timeMemory
142743DrumpfTheGodEmperorGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
415 ms196212 KiB
#include <bits/stdc++.h> #define bp __builtin_popcountll #define pb push_back #define in(s) freopen(s, "r", stdin); #define out(s) freopen(s, "w", stdout); #define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\ freopen((string(s) + "." + end2).c_str(), "w", stdout); #define fi first #define se second #define bw(i, r, l) for (int i = r - 1; i >= l; i--) #define fw(i, l, r) for (int i = l; i < r; i++) #define fa(i, x) for (auto i: x) using namespace std; const int mod = 1e9 + 7, inf = 1061109567; const long long infll = 4557430888798830399; const int N = 405; int n, dp[N][405][N][3], cntPrefix[N][3]; string s; vector<int> reds, greens, yellows; int getRealPosition(int ogPos, int prvRed, int prvGreen, int prvYellow) { //prvRed - cntPrefix[ogPos][0] is the number of reds that are moved to before ogPos int ans = 0; ans += max(0, prvRed - cntPrefix[ogPos][0]); ans += max(0, prvGreen - cntPrefix[ogPos][1]); ans += max(0, prvYellow - cntPrefix[ogPos][2]); return ogPos + ans + 1; //Difference between array indices and dp indices. } signed main() { #ifdef BLU in("blu.inp"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> s; fw (i, 0, s.length()) { if (s[i] == 'R') reds.pb(i); else if (s[i] == 'G') greens.pb(i); else yellows.pb(i); } //0: red, 1: green, 2: yellow fw (i, 0, s.length()) { fw (color, 0, 3) cntPrefix[i][color] = (i ? cntPrefix[i - 1][color] : 0); if (s[i] == 'R') cntPrefix[i][0]++; else if (s[i] == 'G') cntPrefix[i][1]++; else cntPrefix[i][2]++; } fw (r, 0, n + 1) fw (g, 0, n + 1) fw (color, 0, 3) dp[1][r][g][color] = inf; //dp(i, r, g, color): Minimal cost for the first i items, j reds and k greens, i - j - k yellows. The //last leave is colored "color". if (reds.size() > 0) dp[1][1][0][0] = reds[0]; if (greens.size() > 0) dp[1][0][1][1] = greens[0]; if (yellows.size() > 0) dp[1][0][0][2] = yellows[0]; fw (i, 2, n + 1) fw (r, 0, min((i + 1) / 2, (int)reds.size()) + 1) fw (g, 0, min(i - r, (int)greens.size()) + 1) fw (color, 0, 3) { // cout << "dp[" << i << "][" << r << "][" << g << "][" << color << "]\n"; dp[i][r][g][color] = inf; if (color == 0 && r == 0) continue; if (color == 1 && g == 0) continue; if (color == 2 && i - r - g == 0) continue; fw (prvColor, 0, 3) if (prvColor != color) { int newr = r, newg = g; if (color == 0) newr--; if (color == 1) newg--; if (newr < 0 || newg < 0) continue; if (i - 1 - newr - newg < 0) continue; if (newr > i / 2) continue; // cout << "prv state = " << i - 1 << " " << newr << " " << newg << " " << prvColor << " dp = " << dp[i - 1][newr][newg][prvColor] << "\n"; dp[i][r][g][color] = min(dp[i][r][g][color], dp[i - 1][newr][newg][prvColor]); } if (dp[i][r][g][color] == inf) continue; //Non - valid state int y = i - r - g; if (y > yellows.size()) continue; if (color == 0) { dp[i][r][g][color] += getRealPosition(reds[r - 1], r - 1, g, y) - i; } else if (color == 1) { dp[i][r][g][color] += getRealPosition(greens[g - 1], r, g - 1, y) - i; } else { dp[i][r][g][color] += getRealPosition(yellows[y - 1], r, g, y - 1) - i; } } // fw (i, 1, n + 1) fw (r, 0, n + 1) fw (g, 0, n + 1) fw (color, 0, 3) { // cout << "dp[" << i << "][" << r << "][" << g << "][" << color << "] = " << dp[i][r][g][color] << "\n"; // } if (reds.size() > (n + 1) / 2) { cout << "-1"; return 0; } if (greens.size() > (n + 1) / 2) { cout << "-1"; return 0; } if (yellows.size() > (n + 1) / 2) { cout << "-1"; return 0; } int ans = inf; fw (color, 0, 3) ans = min(ans, dp[n][reds.size()][greens.size()][color]); if (ans == inf) cout << "-1"; else cout << ans; return 0; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fw(i, l, r) for (int i = l; i < r; i++)
joi2019_ho_t3.cpp:34:6:
  fw (i, 0, s.length()) {
      ~~~~~~~~~~~~~~~~                  
joi2019_ho_t3.cpp:34:2: note: in expansion of macro 'fw'
  fw (i, 0, s.length()) {
  ^~
joi2019_ho_t3.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fw(i, l, r) for (int i = l; i < r; i++)
joi2019_ho_t3.cpp:40:6:
  fw (i, 0, s.length()) {
      ~~~~~~~~~~~~~~~~                  
joi2019_ho_t3.cpp:40:2: note: in expansion of macro 'fw'
  fw (i, 0, s.length()) {
  ^~
joi2019_ho_t3.cpp:71:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (y > yellows.size()) continue;
       ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (reds.size() > (n + 1) / 2) {
      ~~~~~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (greens.size() > (n + 1) / 2) {
      ~~~~~~~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (yellows.size() > (n + 1) / 2) {
      ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...