제출 #870229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870229		ToighetLPHM	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	83 ms	700088 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 405
using namespace std;
int n;
string s;
int F[N][N][N][3];
vector < int > pos[3];
int C[N][N];
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    cin>>s;
    s='*'+s;
    FOR(i,0,2) pos[i].pb(0);
    FOR(i,1,n)
    if (s[i]=='R') pos[0].pb(i);
    else
    if (s[i]=='G') pos[1].pb(i);
    else pos[2].pb(i);
    int R=pos[0].size()-1,G=pos[1].size()-1,Y=pos[2].size()-1;
    //
    for (auto i : pos[0]) {
        int cnt=0;
        for (auto j : pos[1]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
        cnt=0;
        for (auto j : pos[2]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
    }
    //
    for (auto i : pos[1]) {
        int cnt=0;
        for (auto j : pos[0]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
        cnt=0;
        for (auto j : pos[2]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
    }
    //
    for (auto i : pos[2]) {
        int cnt=0;
        for (auto j : pos[0]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
        cnt=0;
        for (auto j : pos[1]) {
            if (j>i) ++cnt;
            C[i][j]=cnt;
        }
    }
    //
    FOR(i,0,R)
    FOR(j,0,G)
    FOR(k,0,Y)
    FOR(c,0,2) F[i][j][k][c]=INT_MAX;
    int MAX=INT_MAX;
    FOR(i,0,2) F[0][0][0][i]=0;
    FOR(i,0,R)
    FOR(j,0,G)
    FOR(k,0,Y) {
        if (i>0) F[i][j][k][0]=min(F[i-1][j][k][1],F[i-1][j][k][2])+C[pos[0][i]][pos[1][j]]+C[pos[0][i]][pos[2][k]];
        if (j>0) F[i][j][k][1]=min(F[i][j-1][k][0],F[i][j-1][k][2])+C[pos[1][j]][pos[0][i]]+C[pos[1][j]][pos[2][k]];
        if (k>0) F[i][j][k][2]=min(F[i][j][k-1][0],F[i][j][k-1][1])+C[pos[2][k]][pos[0][i]]+C[pos[2][k]][pos[1][j]];
    }
    FOR(i,0,2) MAX=min(MAX,F[R][G][Y][i]);
    if (MAX==INT_MAX) return cout<<-1,0;
    cout<<MAX;
    return 0;
}

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