Submission #870219

#	Time	Username	Problem	Language	Result	Execution time	Memory
870219		ToighetLPHM	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1 ms	2396 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;
const int INF = 0x3f3f3f3f;
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) {
        pos[(s[i]=='R' ? 0 : ((s[i]=='G') ? 1 : 2))].pb(i);
    }
    int R=pos[0].size()-1,G=pos[1].size()-1,Y=pos[2].size()-1;
    if (R+G+Y<=2*max({R,G,Y})) return cout<<-1,0;
    //
    FOR(i,1,n)
        FOR(j,0,2) {
            int cnt=0;
            for (auto k : pos[j]) {
                if (k>i) ++cnt;
                C[i][k]=cnt;
            }
        }
    //
    FOR(i,0,n) C[0][i]=0;
    //
    memset(F,+INF,sizeof(F));
    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]);
    cout<<MAX;
    return 0;
}

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