Submission #753454

#	Time	Username	Problem	Language	Result	Execution time	Memory
753454		IvanJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	75 ms	162984 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 405, inf = 1e9;

int n;
char s[maxn];
int c[maxn];
int dp[maxn][maxn][maxn][3];
int num[maxn][3];
vector<int> p[3];

int cost(int x, int y, int z, int C) {
	int pos;
	if(C == 0) pos = p[C][x];
	if(C == 1) pos = p[C][y];
	if(C == 2) pos = p[C][z];
	
	int ret = min(x, num[pos][0]) + min(y, num[pos][1]) + min(z, num[pos][2]);
	ret = pos - ret;
	return ret;
}

int main() {
	scanf("%d%s", &n, s);
	vector<int> cnt(3, 0);
	for(int i = 0;i < n;i++) {
		if(s[i] == 'R') c[i] = 0;
		if(s[i] == 'G') c[i] = 1;
		if(s[i] == 'Y') c[i] = 2;	
	}
	for(int i = 0;i < n;i++) {
		cnt[c[i]]++, p[c[i]].pb(i);
		for(int j = 0;j < 3;j++) num[i][j] = cnt[j];	
	}
	
	for(int i = 0;i <= cnt[0];i++) 
		for(int j = 0;j <= cnt[1];j++) 
			for(int k = 0;k <= cnt[2];k++) 
				for(int l = 0;l < 3;l++) 
					dp[i][j][k][l] = inf;
	
	for(int i = 0;i < 3;i++) 
		dp[0][0][0][i] = 0;
	
	for(int i = 0;i <= cnt[0];i++)
		for(int j = 0;j <= cnt[1];j++) 
			for(int k = 0;k <= cnt[2];k++) 
				for(int a = 0;a < 3;a++) {
					if(dp[i][j][k][a] == inf) continue;
					if(a != 0 && i < cnt[0]) 
						dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][a] + cost(i, j, k, 0));
					if(a != 1 && j < cnt[1]) 
						dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][a] + cost(i, j, k, 1));	
					if(a != 2 && k < cnt[2]) 
						dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][a] + cost(i, j, k, 2));
				}
	
	int ans = inf;
	for(int i = 0;i < 3;i++) 
		ans = min(dp[cnt[0]][cnt[1]][cnt[2]][i], ans);
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%s", &n, s);
      |  ~~~~~^~~~~~~~~~~~~~~

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