Submission #1194665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194665		nekolie	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	22 ms	28752 KiB

joi2019_ho_t3

// Papryko, daj lepsze zadanka
#include <bits/stdc++.h>
using namespace std;

int n,r,g,y, ile[400][3], inf = 1000000000;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s; cin >> n >> s;
    vector<int> ind[3];
    for (int i = 0; i < n; i++) {
        if (i > 0)
            ile[i][0] = ile[i-1][0], ile[i][1] = ile[i-1][1], ile[i][2] = ile[i-1][2];
        if (s[i] == 'R')
            r++, ile[i][0]++, ind[0].push_back(i);
        else if (s[i] == 'G')
            g++, ile[i][1]++, ind[1].push_back(i);
        else
            y++, ile[i][2]++, ind[2].push_back(i);
    }
    int dp[r+1][g+1][y+1][3];
    for (int i = 0; i <= r; i++) {
        for (int j = 0; j <= g; j++) {
            for (int k = 0; k <= y; k++) {
                if (max({i,j,k}) == 0)
                    dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = 0;
                else if (2*max({i,j,k}) - (i+j+k) - (i+j+k)%2 > 0)
                    dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
                else {
                    dp[i][j][k][0] = ((i > 0) ? min(dp[i-1][j][k][1],dp[i-1][j][k][2]) + max(0,ile[ind[0][i-1]][1]-j) + max(0,ile[ind[0][i-1]][2]-k) : inf);
                    dp[i][j][k][1] = ((j > 0) ? min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + max(0,ile[ind[1][j-1]][0]-i) + max(0,ile[ind[1][j-1]][2]-k) : inf);
                    dp[i][j][k][2] = ((k > 0) ? min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + max(0,ile[ind[2][k-1]][0]-i) + max(0,ile[ind[2][k-1]][1]-j) : inf);
                    dp[i][j][k][0] = min(dp[i][j][k][0],inf), dp[i][j][k][1] = min(dp[i][j][k][1],inf), dp[i][j][k][2] = min(dp[i][j][k][2],inf);
                }
            }
        }
    }
    if (min({dp[r][g][y][0],dp[r][g][y][1],dp[r][g][y][2]}) >= inf)
        cout << -1 << endl;
    else
        cout << min({dp[r][g][y][0],dp[r][g][y][1],dp[r][g][y][2]}) << endl;
    return 0;
}

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