oj.uz

Submission #775896

# Submission time Handle Problem Language Result Execution time Memory
775896 2023-07-07T06:18:17 Z gun_gan Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 291 ms 792012 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 407;

int N;
int dp[MX][MX][MX][3];

vector<int> R, G, Y;

int f(int r, int g, int y, int c) {
      int pos = r + g + y, res = 1e9;
      if(dp[r][g][y][c] != -1) return dp[r][g][y][c];

      if(pos == N) return dp[r][g][y][c] = 0;

      if(c != 0 && r + 1 < R.size()) {
            res = min(res, f(r + 1, g, y, 0) + max(0, R[r + 1] - pos - 1));
      }

      if(c != 1 && g + 1 < G.size()) {
            res = min(res, f(r, g + 1, y, 1) + max(0, G[g + 1] - pos - 1));
      }
      if(c != 2 && y + 1 < Y.size()) {
            res = min(res, f(r, g, y + 1, 2) + max(0, Y[y + 1] - pos - 1));
      }

      return dp[r][g][y][c] = res;     
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      memset(dp, -1, sizeof dp);
      
      cin >> N;
      R = {0}, G = {0}, Y = {0};

      for(int i = 1; i <= N; i++) {
            char c;
            cin >> c;

            if(c == 'R') R.push_back(i);
            if(c == 'G') G.push_back(i);
            if(c == 'Y') Y.push_back(i);
      }

      int k = min({f(0, 0, 0, 0), f(0, 0, 0, 1), f(0, 0, 0, 2)});
      if(k == 1e9) k = -1;
      cout << k << '\n';
}

Compilation message

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:18:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |       if(c != 0 && r + 1 < R.size()) {
      |                    ~~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |       if(c != 1 && g + 1 < G.size()) {
      |                    ~~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |       if(c != 2 && y + 1 < Y.size()) {
      |                    ~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 791792 KB Output is correct
2 Correct 238 ms 791892 KB Output is correct
3 Correct 237 ms 791920 KB Output is correct
4 Correct 237 ms 791848 KB Output is correct
5 Correct 236 ms 791888 KB Output is correct
6 Correct 242 ms 791880 KB Output is correct
7 Correct 241 ms 791952 KB Output is correct
8 Correct 233 ms 791808 KB Output is correct
9 Correct 245 ms 791804 KB Output is correct
10 Correct 230 ms 791856 KB Output is correct
11 Incorrect 234 ms 791880 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 791792 KB Output is correct
2 Correct 238 ms 791892 KB Output is correct
3 Correct 237 ms 791920 KB Output is correct
4 Correct 237 ms 791848 KB Output is correct
5 Correct 236 ms 791888 KB Output is correct
6 Correct 242 ms 791880 KB Output is correct
7 Correct 241 ms 791952 KB Output is correct
8 Correct 233 ms 791808 KB Output is correct
9 Correct 245 ms 791804 KB Output is correct
10 Correct 230 ms 791856 KB Output is correct
11 Incorrect 234 ms 791880 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 791892 KB Output is correct
2 Correct 234 ms 791936 KB Output is correct
3 Correct 231 ms 791912 KB Output is correct
4 Correct 248 ms 791884 KB Output is correct
5 Correct 236 ms 791832 KB Output is correct
6 Correct 240 ms 792012 KB Output is correct
7 Correct 236 ms 791908 KB Output is correct
8 Correct 233 ms 791828 KB Output is correct
9 Correct 237 ms 791936 KB Output is correct
10 Correct 263 ms 791936 KB Output is correct
11 Correct 270 ms 791884 KB Output is correct
12 Correct 239 ms 791932 KB Output is correct
13 Correct 254 ms 791864 KB Output is correct
14 Correct 235 ms 791884 KB Output is correct
15 Correct 236 ms 791936 KB Output is correct
16 Correct 233 ms 791880 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 791792 KB Output is correct
2 Correct 238 ms 791892 KB Output is correct
3 Correct 237 ms 791920 KB Output is correct
4 Correct 237 ms 791848 KB Output is correct
5 Correct 236 ms 791888 KB Output is correct
6 Correct 242 ms 791880 KB Output is correct
7 Correct 241 ms 791952 KB Output is correct
8 Correct 233 ms 791808 KB Output is correct
9 Correct 245 ms 791804 KB Output is correct
10 Correct 230 ms 791856 KB Output is correct
11 Incorrect 234 ms 791880 KB Output isn't correct
12 Halted 0 ms 0 KB -