oj.uz

Submission #120420

# Submission time Handle Problem Language Result Execution time Memory
120420 2019-06-24T12:41:20 Z Just_Solve_The_Problem Growing Vegetable is Fun 3 (JOI19_ho_t3) C++11
15 / 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][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

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 640 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Incorrect 2 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 13 ms 640 KB Output is correct
3 Correct 13 ms 612 KB Output is correct
4 Correct 13 ms 640 KB Output is correct
5 Correct 13 ms 684 KB Output is correct
6 Correct 13 ms 640 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 13 ms 640 KB Output is correct
9 Correct 13 ms 640 KB Output is correct
10 Correct 13 ms 640 KB Output is correct
11 Correct 13 ms 640 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 9 ms 640 KB Output is correct
14 Correct 10 ms 640 KB Output is correct
15 Correct 13 ms 760 KB Output is correct
16 Correct 13 ms 640 KB Output is correct

Subtask #4
0 / 25.0

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