oj.uz

Submission #818788

# Submission time Handle Problem Language Result Execution time Memory
818788 2023-08-10T06:45:20 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 1040344 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];
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) {
            auto gg = upper_bound(G.begin(), G.end(), R[r]) - G.begin();
            auto yy = upper_bound(Y.begin(), Y.end(), R[r]) - Y.begin();

            int cost = max(0, (int)gg - g) + max(0, (int)yy - y);
            res = min(res, f(r + 1, g, y, 0) + cost);
      }
      if(g < G.size() && l != 1) {
            auto rr = upper_bound(R.begin(), R.end(), G[g]) - R.begin();
            auto yy = upper_bound(Y.begin(), Y.end(), G[g]) - Y.begin();

            int cost = max(0, (int)rr - r) + max(0, (int)yy - y);
            res = min(res, f(r, g + 1, y, 1) + cost);
      }
      if(y < Y.size() && l != 2) {
            auto rr = upper_bound(R.begin(), R.end(), Y[y]) - R.begin();
            auto gg = upper_bound(G.begin(), G.end(), Y[y]) - G.begin();

            int cost = max(0, (int)rr - r) + max(0, (int)gg - 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);
            }
            if(s[i] == 'G') {
                  G.push_back(i);
            }
            if(s[i] == 'Y') {
                  Y.push_back(i);
            }
      }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 1040280 KB Output is correct
2 Correct 303 ms 1040224 KB Output is correct
3 Execution timed out 557 ms 1040216 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 1040280 KB Output is correct
2 Correct 303 ms 1040224 KB Output is correct
3 Execution timed out 557 ms 1040216 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 1040296 KB Output is correct
2 Correct 360 ms 1040248 KB Output is correct
3 Correct 357 ms 1040232 KB Output is correct
4 Correct 400 ms 1040228 KB Output is correct
5 Correct 314 ms 1040240 KB Output is correct
6 Correct 315 ms 1040216 KB Output is correct
7 Correct 327 ms 1040344 KB Output is correct
8 Correct 340 ms 1040320 KB Output is correct
9 Correct 333 ms 1040228 KB Output is correct
10 Correct 339 ms 1040304 KB Output is correct
11 Correct 323 ms 1040324 KB Output is correct
12 Correct 325 ms 1040208 KB Output is correct
13 Correct 328 ms 1040220 KB Output is correct
14 Correct 359 ms 1040264 KB Output is correct
15 Correct 347 ms 1040256 KB Output is correct
16 Correct 333 ms 1040248 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 1040280 KB Output is correct
2 Correct 303 ms 1040224 KB Output is correct
3 Execution timed out 557 ms 1040216 KB Time limit exceeded
4 Halted 0 ms 0 KB -