oj.uz

Submission #775900

# Submission time Handle Problem Language Result Execution time Memory
775900 2023-07-07T06:22:48 Z gun_gan Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 332 ms 792052 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 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 332 ms 791824 KB Output is correct
2 Correct 246 ms 791788 KB Output is correct
3 Correct 244 ms 791936 KB Output is correct
4 Correct 245 ms 791848 KB Output is correct
5 Correct 253 ms 791888 KB Output is correct
6 Correct 241 ms 791832 KB Output is correct
7 Correct 244 ms 791884 KB Output is correct
8 Correct 244 ms 791888 KB Output is correct
9 Correct 243 ms 791832 KB Output is correct
10 Correct 288 ms 791828 KB Output is correct
11 Incorrect 252 ms 791884 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 791824 KB Output is correct
2 Correct 246 ms 791788 KB Output is correct
3 Correct 244 ms 791936 KB Output is correct
4 Correct 245 ms 791848 KB Output is correct
5 Correct 253 ms 791888 KB Output is correct
6 Correct 241 ms 791832 KB Output is correct
7 Correct 244 ms 791884 KB Output is correct
8 Correct 244 ms 791888 KB Output is correct
9 Correct 243 ms 791832 KB Output is correct
10 Correct 288 ms 791828 KB Output is correct
11 Incorrect 252 ms 791884 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 246 ms 791820 KB Output is correct
2 Correct 239 ms 791832 KB Output is correct
3 Correct 237 ms 791900 KB Output is correct
4 Correct 245 ms 791852 KB Output is correct
5 Correct 242 ms 791884 KB Output is correct
6 Correct 239 ms 791924 KB Output is correct
7 Correct 249 ms 791836 KB Output is correct
8 Correct 241 ms 791936 KB Output is correct
9 Correct 242 ms 791920 KB Output is correct
10 Correct 250 ms 792052 KB Output is correct
11 Correct 246 ms 791876 KB Output is correct
12 Correct 248 ms 791804 KB Output is correct
13 Correct 244 ms 791904 KB Output is correct
14 Correct 243 ms 791912 KB Output is correct
15 Correct 244 ms 791872 KB Output is correct
16 Correct 282 ms 791936 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 791824 KB Output is correct
2 Correct 246 ms 791788 KB Output is correct
3 Correct 244 ms 791936 KB Output is correct
4 Correct 245 ms 791848 KB Output is correct
5 Correct 253 ms 791888 KB Output is correct
6 Correct 241 ms 791832 KB Output is correct
7 Correct 244 ms 791884 KB Output is correct
8 Correct 244 ms 791888 KB Output is correct
9 Correct 243 ms 791832 KB Output is correct
10 Correct 288 ms 791828 KB Output is correct
11 Incorrect 252 ms 791884 KB Output isn't correct
12 Halted 0 ms 0 KB -