Submission #120421

#	Time	Username	Problem	Language	Result	Execution time	Memory
120421		Just_Solve_The_Problem	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	31 ms	760 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][3];
int n;
string S;
int s[N];
int asd[10];

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;
  }
  
  for (int mask = 1; mask < 8; mask++) {
    for (int j = 0; j < 3; j++) {
      if ((mask >> j) & 1) {
        asd[mask] = j;
      }
    }
  }
  dp[1][1][1 << s[1]][s[1]] = 0;
  for (int i = 1; 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 = 1; mask < 8; mask++) {
        for (int last = 0; last < 3; 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]][asd[mask]] = min(dp[nxt][j][1 << s[i + 1]][asd[mask]], res); 
          }
        }
      }
    }
  }
  int ans = 1e9 + 2;
  for (int i = 1; i < 5; i++)
    for (int j = 0; j < 3; j++)
      ans = min(ans, dp[n & 1][1][i][j]);
  if (ans > 1e9)
    ans = -1;
  cout << ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:17: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:38:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     int nxt = (i & 1 ^ 1);
                ~~^~~
joi2019_ho_t3.cpp:19: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:26:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     s[i + 1] = x;
     ~~~~~~~~~^~~

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