Submission #341567

#	Time	Username	Problem	Language	Result	Execution time	Memory
341567		limabeans	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	115 ms	162924 KiB

joi2019_ho_t3

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 444;
const int inf = 1e9;


int n;
string s;
int a[maxn];
int dp[maxn][maxn][maxn][3];

vector<int> inds[maxn];
int prevs[3][maxn]; // prev[j][i]: # of j's in a[0...i-1]

void upd(int &x, int y) {
    x=min(x,y);
}


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

    cin>>n;
    cin>>s;
    for (int i=0; i<n; i++) {
	if (s[i]=='R') {
	    a[i]=0;
	} else if (s[i]=='G') {
	    a[i]=1;
	} else if (s[i]=='Y') {
	    a[i]=2;
	} else assert(false);
    }

    for (int i=0; i<n; i++) {
	inds[a[i]].push_back(i);
	for (int j=0; j<3; j++) {
	    prevs[j][i] = inds[j].size();
	}
    }

    for (int a=0; a<=(int)inds[0].size(); a++) {
	for (int b=0; b<=(int)inds[1].size(); b++) {
	    for (int c=0; c<=(int)inds[2].size(); c++) {
		for (int last=0; last<3; last++) {
		    dp[a][b][c][last] = inf;
		}
	    }
	}
    }

    for (int last=0; last<3; last++) {
	dp[0][0][0][last] = 0;
    }

    

    for (int a=0; a<=(int)inds[0].size(); a++) {
	for (int b=0; b<=(int)inds[1].size(); b++) {
	    for (int c=0; c<=(int)inds[2].size(); c++) {
		for (int last=0; last<3; last++) {
		    // place R
		    // to place it, need to swap past all the G and Y's
		    if (a<(int)inds[0].size() && last!=0) {
			int p = inds[0][a];
			int cur = dp[a][b][c][last] + max(0, prevs[1][p]-b) + max(0, prevs[2][p]-c);
			upd(dp[a+1][b][c][0], cur);
		    }
		    // place G
		    if (b<(int)inds[1].size() && last!=1) {
			int p = inds[1][b];
			int cur = dp[a][b][c][last] + max(0, prevs[0][p]-a) + max(0, prevs[2][p]-c);
			upd(dp[a][b+1][c][1], cur);
		    }
		    // place Y
		    if (c<(int)inds[2].size() && last!=2) {
			int p = inds[2][c];
			int cur = dp[a][b][c][last] + max(0, prevs[0][p]-a) + max(0, prevs[1][p]-b);
			upd(dp[a][b][c+1][2], cur);
		    }
		}
	    }
	}
    }

    int res = inf; 
    for (int i=0; i<3; i++) {
	res = min(res, dp[(int)inds[0].size()][(int)inds[1].size()][(int)inds[2].size()][i]);
    }

    if (res > inf/2) res = -1;
    out(res);
    
    return 0;
}

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