oj.uz

Submission #174400

# Submission time Handle Problem Language Result Execution time Memory
174400 2020-01-06T11:22:29 Z AlexLuchianov Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
60 / 100
 500 ms 246728 KB 
#include <iostream>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 401;
int dp[1 + nmax][1 + nmax][1 + nmax][4];
int v[1 + nmax];
int lower[1 + nmax][4];
int pos[1 + nmax][4];

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++) {
    char ch;
    cin >> ch;
    if(ch == 'R')
      v[i] = 1;
    else if(ch == 'G')
      v[i] = 2;
    else if(ch == 'Y')
      v[i] = 3;
   lower[i][1] += lower[i - 1][1];
   lower[i][2] += lower[i - 1][2];
   lower[i][3] += lower[i - 1][3];
   lower[i][v[i]]++;
   pos[lower[i][v[i]]][v[i]] = i;
  }

  int red = lower[n][1], green = lower[n][2], yellow = lower[n][3];
  for(int i = 0; i <= red; i++)
    for(int j = 0; j <= green; j++)
      for(int h = 0; h <= yellow; h++)
        for(int last = 1; last <= 3; last++)
          dp[i][j][h][last] = nmax * nmax;
  dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][3] = 0;

  for(int total = 0; total < n; total++)
    for(int i = 0; i <= red; i++)
      for(int j = 0; j <= green; j++)
        if(i + j <= total){
          int h = total - i - j;
          if(i < red){
            int pos2 = pos[i + 1][1];
            dp[i + 1][j][h][1] = MIN(dp[i + 1][j][h][1], MIN(dp[i][j][h][2], dp[i][j][h][3]) +
                                  MAX(0, lower[pos2][2] - j) +
                                  MAX(0, lower[pos2][3] - h)
                                  );
          }
          if(j < green){
            int pos2 = pos[j + 1][2];
            dp[i][j + 1][h][2] = MIN(dp[i][j + 1][h][2], MIN(dp[i][j][h][1], dp[i][j][h][3]) +
                                  MAX(0, lower[pos2][1] - i) +
                                  MAX(0, lower[pos2][3] - h)
                                  );
          }
          if(h < yellow){
            int pos2 = pos[h + 1][3];
            dp[i][j][h + 1][3] = MIN(dp[i][j][h + 1][3], MIN(dp[i][j][h][1], dp[i][j][h][2]) +
                                  MAX(0, lower[pos2][1] - i) +
                                  MAX(0, lower[pos2][2] - j)
                                  );
          }
        }
  int result = MIN(dp[red][green][yellow][1], MIN(dp[red][green][yellow][2], dp[red][green][yellow][3]));
  if(result == nmax * nmax)
    cout << -1;
  else
    cout << result;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 4 ms 2552 KB Output is correct
19 Correct 4 ms 2040 KB Output is correct
20 Correct 4 ms 2424 KB Output is correct
21 Correct 4 ms 2684 KB Output is correct
22 Correct 3 ms 1788 KB Output is correct
23 Correct 4 ms 2296 KB Output is correct
24 Correct 4 ms 1784 KB Output is correct
25 Correct 6 ms 4344 KB Output is correct
26 Correct 6 ms 4600 KB Output is correct
27 Correct 5 ms 3320 KB Output is correct
28 Correct 4 ms 2552 KB Output is correct
29 Correct 4 ms 2424 KB Output is correct
30 Correct 4 ms 2424 KB Output is correct
31 Correct 4 ms 2168 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 6 ms 4344 KB Output is correct
34 Correct 5 ms 3960 KB Output is correct
35 Correct 4 ms 2936 KB Output is correct
36 Correct 4 ms 2040 KB Output is correct
37 Correct 3 ms 1912 KB Output is correct
38 Correct 4 ms 2296 KB Output is correct
39 Correct 4 ms 2536 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 4 ms 2424 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Execution timed out 556 ms 246728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 4 ms 2552 KB Output is correct
19 Correct 4 ms 2040 KB Output is correct
20 Correct 4 ms 2424 KB Output is correct
21 Correct 4 ms 2684 KB Output is correct
22 Correct 3 ms 1788 KB Output is correct
23 Correct 4 ms 2296 KB Output is correct
24 Correct 4 ms 1784 KB Output is correct
25 Correct 6 ms 4344 KB Output is correct
26 Correct 6 ms 4600 KB Output is correct
27 Correct 5 ms 3320 KB Output is correct
28 Correct 4 ms 2552 KB Output is correct
29 Correct 4 ms 2424 KB Output is correct
30 Correct 4 ms 2424 KB Output is correct
31 Correct 4 ms 2168 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 6 ms 4344 KB Output is correct
34 Correct 5 ms 3960 KB Output is correct
35 Correct 4 ms 2936 KB Output is correct
36 Correct 4 ms 2040 KB Output is correct
37 Correct 3 ms 1912 KB Output is correct
38 Correct 4 ms 2296 KB Output is correct
39 Correct 4 ms 2536 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 4 ms 2424 KB Output is correct
42 Correct 2 ms 380 KB Output is correct
43 Execution timed out 556 ms 246728 KB Time limit exceeded
44 Halted 0 ms 0 KB -