Submission #432348

#	Time	Username	Problem	Language	Result	Execution time	Memory
432348		Josia	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	1 ms	332 KiB

joi2019_ho_t3

#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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25