oj.uz

Submission #818819

# Submission time Handle Problem Language Result Execution time Memory
818819 2023-08-10T06:51:15 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 1040352 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 405;

int N;
string s;
int dp[MX][MX][MX][4];
int cnt[MX][3]; //R = 0, G = 1, Y = 2
vector<int> R, G, Y;

int f(int r, int g, int y, int l) {
      if(r + g + y == N) return 0;
      if(dp[r][g][y][l] != -1) return dp[r][g][y][l];

      int res = 1e9;
      if(r < R.size() && l != 0) {
            int cost = max(0, cnt[R[r]][1] - g) + max(0, cnt[R[r]][2] - y);
            res = min(res, f(r + 1, g, y, 0) + cost);
      }
      if(g < G.size() && l != 1) {
            int cost = max(0, cnt[G[g]][0] - r) + max(0, cnt[G[g]][2] - y);
            res = min(res, f(r, g + 1, y, 1) + cost);
      }
      if(y < Y.size() && l != 2) {
            int cost = max(0, cnt[Y[y]][0] - r) + max(0, cnt[Y[y]][1] - g);
            res = min(res, f(r, g, y + 1, 2) + cost);
      }

      // cout << r << " " << g << " " << y << " = " << res << '\n';

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

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

      memset(dp, -1, sizeof dp);

      cin >> N >> s;

      for(int i = 0; i < N; i++) {
            if(s[i] == 'R') {
                  R.push_back(i);
                  cnt[i][0]++;
            }
            if(s[i] == 'G') {
                  G.push_back(i);
                  cnt[i][1]++;
            }
            if(s[i] == 'Y') {
                  Y.push_back(i);
                  cnt[i][2]++;
            }

            if(i > 0) {
                  cnt[i][0] += cnt[i - 1][0];
                  cnt[i][1] += cnt[i - 1][1];
                  cnt[i][2] += cnt[i - 1][2];
            }
      }

      int k = f(0, 0, 0, 3);
      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:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |       if(r < R.size() && l != 0) {
      |          ~~^~~~~~~~~~
joi2019_ho_t3.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |       if(g < G.size() && l != 1) {
      |          ~~^~~~~~~~~~
joi2019_ho_t3.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |       if(y < Y.size() && l != 2) {
      |          ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 1040220 KB Output is correct
2 Correct 300 ms 1040296 KB Output is correct
3 Correct 332 ms 1040208 KB Output is correct
4 Correct 300 ms 1040256 KB Output is correct
5 Correct 313 ms 1040284 KB Output is correct
6 Correct 315 ms 1040288 KB Output is correct
7 Correct 310 ms 1040208 KB Output is correct
8 Correct 372 ms 1040196 KB Output is correct
9 Correct 330 ms 1040204 KB Output is correct
10 Correct 329 ms 1040260 KB Output is correct
11 Correct 309 ms 1040232 KB Output is correct
12 Execution timed out 505 ms 1040200 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 1040220 KB Output is correct
2 Correct 300 ms 1040296 KB Output is correct
3 Correct 332 ms 1040208 KB Output is correct
4 Correct 300 ms 1040256 KB Output is correct
5 Correct 313 ms 1040284 KB Output is correct
6 Correct 315 ms 1040288 KB Output is correct
7 Correct 310 ms 1040208 KB Output is correct
8 Correct 372 ms 1040196 KB Output is correct
9 Correct 330 ms 1040204 KB Output is correct
10 Correct 329 ms 1040260 KB Output is correct
11 Correct 309 ms 1040232 KB Output is correct
12 Execution timed out 505 ms 1040200 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 1040204 KB Output is correct
2 Correct 316 ms 1040320 KB Output is correct
3 Correct 366 ms 1040272 KB Output is correct
4 Correct 311 ms 1040340 KB Output is correct
5 Correct 320 ms 1040312 KB Output is correct
6 Correct 344 ms 1040212 KB Output is correct
7 Correct 331 ms 1040232 KB Output is correct
8 Correct 313 ms 1040228 KB Output is correct
9 Correct 335 ms 1040284 KB Output is correct
10 Correct 307 ms 1040252 KB Output is correct
11 Correct 314 ms 1040336 KB Output is correct
12 Correct 307 ms 1040352 KB Output is correct
13 Correct 320 ms 1040204 KB Output is correct
14 Correct 322 ms 1040332 KB Output is correct
15 Correct 305 ms 1040336 KB Output is correct
16 Correct 313 ms 1040248 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 1040220 KB Output is correct
2 Correct 300 ms 1040296 KB Output is correct
3 Correct 332 ms 1040208 KB Output is correct
4 Correct 300 ms 1040256 KB Output is correct
5 Correct 313 ms 1040284 KB Output is correct
6 Correct 315 ms 1040288 KB Output is correct
7 Correct 310 ms 1040208 KB Output is correct
8 Correct 372 ms 1040196 KB Output is correct
9 Correct 330 ms 1040204 KB Output is correct
10 Correct 329 ms 1040260 KB Output is correct
11 Correct 309 ms 1040232 KB Output is correct
12 Execution timed out 505 ms 1040200 KB Time limit exceeded
13 Halted 0 ms 0 KB -