제출 #1187485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187485		maxFedorchuk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	61 ms	163216 KiB

joi2019_ho_t3

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

const int MX=450,INF=1e9;

int dp[MX][MX][MX][3];

int rpr[MX],gpr[MX],ypr[MX];
vector < int > inr,ing,iny;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    string s;
    int n;
    cin>>n>>s;
    s="*"+s;

    for(int i=1;i<=n;i++)
    {
        rpr[i]=rpr[i-1];
        if(s[i]=='R')
        {
            inr.push_back(i);
            rpr[i]++;
        }

        gpr[i]=gpr[i-1];
        if(s[i]=='G')
        {
            ing.push_back(i);
            gpr[i]++;
        }

        ypr[i]=ypr[i-1];
        if(s[i]=='Y')
        {
            iny.push_back(i);
            ypr[i]++;
        }
    }

    for(int r=0;r<=inr.size();r++)
    {
        for(int g=0;g<=ing.size();g++)
        {
            for(int y=0;y<=iny.size();y++)
            {
                dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=INF;

                if(r+g+y==0)
                {
                    dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=0;
                    continue;
                }

                if(r!=0)
                {
                    dp[r][g][y][0]=min(INF,min(dp[r-1][g][y][1],dp[r-1][g][y][2])+max(0,gpr[inr[r-1]]-g)+max(0,ypr[inr[r-1]]-y));
                }

                if(g!=0)
                {
                    dp[r][g][y][1]=min(INF,min(dp[r][g-1][y][0],dp[r][g-1][y][2])+max(0,rpr[ing[g-1]]-r)+max(0,ypr[ing[g-1]]-y));
                }
                
                if(y!=0)
                {
                    dp[r][g][y][2]=min(INF,min(dp[r][g][y-1][0],dp[r][g][y-1][1])+max(0,rpr[iny[y-1]]-r)+max(0,gpr[iny[y-1]]-g));
                }
            }
        }
    }

    int ans=min({dp[inr.size()][ing.size()][iny.size()][0],dp[inr.size()][ing.size()][iny.size()][1],dp[inr.size()][ing.size()][iny.size()][2]});
    
    cout<<((ans==INF)?-1:ans)<<"\n";
    return 0;
}

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