Submission #1282222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282222		SSKMF	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	128 ms	1296 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

inline int Query (vector <int>& sir , int stanga , int dreapta , const int minim)
{
    const int initial = dreapta;
    while (stanga <= dreapta)
    {
        const int mijloc = (stanga + dreapta) >> 1;
        if (sir[mijloc] >= minim) { dreapta = mijloc - 1; }
        else { stanga = mijloc + 1; }
    }

    return initial - dreapta;
}

vector <int> aparitii[3];
int minim[401][401][3];
char sir[401];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime;
    cin >> lungime >> sir;

    for (int indice = 0 ; indice < lungime ; indice++) {
        if (sir[indice] == 'R') { aparitii[0].push_back(indice + 1); }
        else if (sir[indice] == 'G') { aparitii[1].push_back(indice + 1); }
        else { aparitii[2].push_back(indice + 1); }
    }

    for (int luate_1 = 0 ; luate_1 <= (int)aparitii[0].size() ; luate_1++) {
        for (int luate_2 = 0 ; luate_2 <= (int)aparitii[1].size() ; luate_2++) {
            for (int luate_3 = (luate_1 == 0 && luate_2 == 0 ? 1 : 0) ; luate_3 <= (int)aparitii[2].size() ; luate_3++)
            {
                if (!luate_1) { minim[luate_2][luate_3][0] = 1000000000; }
                else { minim[luate_2][luate_3][0] = min(minim[luate_2][luate_3][1] , minim[luate_2][luate_3][2]) + Query(aparitii[1] , 0 , luate_2 - 1 , aparitii[0][luate_1 - 1]) + Query(aparitii[2] , 0 , luate_3 - 1 , aparitii[0][luate_1 - 1]); }
                
                if (!luate_2) { minim[luate_2][luate_3][1] = 1000000000; }
                else { minim[luate_2][luate_3][1] = min(minim[luate_2 - 1][luate_3][0] , minim[luate_2 - 1][luate_3][2]) + Query(aparitii[0] , 0 , luate_1 - 1 , aparitii[1][luate_2 - 1]) + Query(aparitii[2] , 0 , luate_3 - 1 , aparitii[1][luate_2 - 1]); }
                
                if (!luate_3) { minim[luate_2][luate_3][2] = 1000000000; }
                else { minim[luate_2][luate_3][2] = min(minim[luate_2][luate_3 - 1][0] , minim[luate_2][luate_3 - 1][1]) + Query(aparitii[0] , 0 , luate_1 - 1 , aparitii[2][luate_3 - 1]) + Query(aparitii[1] , 0 , luate_2 - 1 , aparitii[2][luate_3 - 1]); }
            } 
        } 
    }
    
    const int rezultat = min({minim[aparitii[1].size()][aparitii[2].size()][0] , minim[aparitii[1].size()][aparitii[2].size()][1] , minim[aparitii[1].size()][aparitii[2].size()][2]});
    cout << (rezultat >= 1000000000 ? -1 : rezultat);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25