oj.uz

Submission #120419

# Submission time Handle Problem Language Result Execution time Memory
120419 2019-06-24T12:40:48 Z Just_Solve_The_Problem Growing Vegetable is Fun 3 (JOI19_ho_t3) C++11
0 / 100
 13 ms 768 KB 
#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) {
        if (asd[mask] == 0)
          asd[mask] = j;
        else
          asd[mask] = -1;
      }
    }
  }
  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 if (asd[mask] != -1) {
            dp[nxt][j][1 << s[i + 1]][asd[mask]] = min(dp[nxt][j][asd[mask]][s[i + 1]], 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

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:41: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Incorrect 7 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Incorrect 7 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Incorrect 13 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Incorrect 7 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -