oj.uz

Submission #432348

# Submission time Handle Problem Language Result Execution time Memory
432348 2021-06-18T08:25:52 Z Josia Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

#define int int64_t

using namespace std;


vector<vector<int>> fromCountToPos (3);



int DP(int n, int color, int count0, int count1) {
    if (n == 0) return 0;

    if (count0 < 0 || count1 < 0 || count0 + count1 > n) return INT32_MAX;
    if (color == 0 && count0 == 0) return INT32_MAX;
    if (color == 1 && count1 == 0) return INT32_MAX;
    if (color == 2 && n-count0-count1 == 0) return INT32_MAX;

    int option1;

    if (color == 0) option1 = DP(n-1, (color+1)%3, count0-1, count1);
    if (color == 1) option1 = DP(n-1, (color+1)%3, count0, count1-1);
    if (color == 2) option1 = DP(n-1, (color+1)%3, count0, count1);


    int option2;

    if (color == 0) option2 = DP(n-1, (color+2)%3, count0-1, count1);
    if (color == 1) option2 = DP(n-1, (color+2)%3, count0, count1-1);
    if (color == 2) option2 = DP(n-1, (color+2)%3, count0, count1);

    int swaplenght;
    if (color == 0) swaplenght = abs((n-1)-fromCountToPos[0][count0-1]);
    if (color == 1) swaplenght = abs((n-1)-fromCountToPos[1][count1-1]);
    if (color == 2) swaplenght = abs((n-1)-fromCountToPos[2][n-count0-count1-1]);

    // cout << option1 << " " << option2 << "\n";
    // cout << color << " " << count0 << " " << count1 << " " << n-count0-count1 << " " << swaplenght << "\n";

    return min(option1, option2)+swaplenght;
}




signed main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);


    int n; cin >> n;
    string s; cin >> s;

    int count0 = 0;
    int count1 = 0;
    int count2 = 0;

    for (int i = 0; i<s.size(); i++) {
        if (s[i] == 'R') {count0++; fromCountToPos[0].push_back(i);}
        if (s[i] == 'G') {count1++; fromCountToPos[1].push_back(i);}
        if (s[i] == 'Y') {count2++; fromCountToPos[2].push_back(i);}
    }

    /*for (auto i: fromCountToPos) {
        for (auto j: i) {
            cout << j << " ";
        }
        cout << "\n";
    }*/


    // cout << DP(n, 0, count0, count1) <<" "<< DP(n, 1, count0, count1) <<" "<< DP(n, 2, count0, count1) << "\n";

    int res = min({DP(n, 0, count0, count1), DP(n, 1, count0, count1), DP(n, 2, count0, count1)});

    if (res >= INT32_MAX) res = -1;
    else res /= 2;

    cout << res << "\n";

    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i<s.size(); i++) {
      |                     ~^~~~~~~~~
joi2019_ho_t3.cpp: In function 'int64_t DP(int64_t, int64_t, int64_t, int64_t)':
joi2019_ho_t3.cpp:27:9: warning: 'option2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     int option2;
      |         ^~~~~~~
joi2019_ho_t3.cpp:20:9: warning: 'option1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |     int option1;
      |         ^~~~~~~
joi2019_ho_t3.cpp:41:34: warning: 'swaplenght' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     return min(option1, option2)+swaplenght;
      |                                  ^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 284 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -