oj.uz

Submission #753454

# Submission time Handle Problem Language Result Execution time Memory
753454 2023-06-05T09:00:15 Z IvanJ Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 75 ms 162984 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Incorrect 1 ms 564 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Incorrect 1 ms 564 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 62 ms 162872 KB Output is correct
3 Correct 58 ms 162128 KB Output is correct
4 Correct 60 ms 162984 KB Output is correct
5 Correct 68 ms 162944 KB Output is correct
6 Correct 75 ms 162972 KB Output is correct
7 Correct 64 ms 162096 KB Output is correct
8 Correct 58 ms 162088 KB Output is correct
9 Correct 63 ms 161280 KB Output is correct
10 Correct 62 ms 162868 KB Output is correct
11 Correct 62 ms 162960 KB Output is correct
12 Correct 20 ms 43948 KB Output is correct
13 Correct 33 ms 77160 KB Output is correct
14 Correct 43 ms 111308 KB Output is correct
15 Incorrect 60 ms 162884 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 564 KB Output is correct
10 Incorrect 1 ms 564 KB Output isn't correct
11 Halted 0 ms 0 KB -