Submission #120411

#	Time	Username	Problem	Language	Result	Execution time	Memory
120411		Just_Solve_The_Problem	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	0 / 100	17 ms	768 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define ll long long
#define ok puts("OK");

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)1500 + 7;

int dp[2][N][1 << 3][4];
int n;
string S;
int s[N];

main() {
  memset(dp, 63, sizeof dp);
  scanf("%d", &n);
  cin >> S;
  for (int i = 0; i < n; i++) {
    int x;
    if (S[i] == 'R') x = 0;
    if (S[i] == 'G') x = 1;
    if (S[i] == 'Y') x = 2;
    s[i + 1] = x;
  }
  dp[0][1][0][3] = 0;
  for (int i = 0; i < n; i++) {
    int nxt = (i & 1 ^ 1);
    memset(dp[nxt], 63, sizeof dp[nxt]);
    for (int j = 1; j <= n; j++) {
      for (int mask = 0; mask < 8; mask++) {
        for (int last = 0; last < 4; last++) {
          int res = dp[i & 1][j][mask][last];
          dp[nxt][j + 1][mask | (1 << s[i + 1])][last] = min(dp[nxt][j + 1][mask | (1 << s[i + 1])][last], res);
          if ((mask >> s[i + 1]) & 1) continue;
          if (last != s[i + 1]) {
            dp[nxt][j][mask][s[i + 1]] = min(dp[nxt][j][mask][s[i + 1]], res + j);
          }
          if (j > 1) {
            dp[nxt][j - 1][mask][s[i + 1]] = min(dp[nxt][j - 1][mask][s[i + 1]], res + j - 1);
          } else {
            dp[nxt][j][1 << s[i + 1]][s[i + 1]] = min(dp[nxt][j][1 << s[i + 1]][s[i + 1]], res); 
          }
        }
      }
    }
  }
  int ans = 1e9 + 2;
  for (int i = 0; i < 8; i++)
    for (int j = 0; j < 4; j++)
      ans = min(ans, dp[n & 1][1][i][j]);
  if (ans > 1e9)
    ans = -1;
  cout << ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:16:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:29:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     int nxt = (i & 1 ^ 1);
                ~~^~~
joi2019_ho_t3.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:25:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     s[i + 1] = x;
     ~~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25