oj.uz

Submission #136906

# Submission time Handle Problem Language Result Execution time Memory
136906 2019-07-26T13:56:43 Z ekrem Growing Vegetable is Fun 3 (JOI19_ho_t3) C++
60 / 100
 14 ms 11256 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define mod 1000000007
#define inf 1000000009
#define N 65

using namespace std;

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

int n, ans, a[N], say[5], dp[N][N][N][5], pre[N][5], yer[5][N];
map < char , int > h;

int f(int r, int g, int y, int lst){
	if(r < 0 or g < 0 or y < 0)
		return inf;
	if(r + g + y == 0)
		return 0;
	int &ans = dp[r][g][y][lst];
	if(ans != -1)
		return ans;
	ans = inf;
	if(lst == 1){//r yapcan
		int ind = yer[1][r];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r - 1, g, y, 2) + of);
		ans = min(ans, f(r - 1, g, y, 3) + of);
	}
	if(lst == 2){//g yapcan
		int ind = yer[2][g];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r, g - 1, y, 1) + of);
		ans = min(ans, f(r, g - 1, y, 3) + of);
		// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
	}
	if(lst == 3){//y yapcan
		int ind = yer[3][y];
		int rr = min(r, pre[ind][1]);
		int gg = min(g, pre[ind][2]);
		int yy = min(y, pre[ind][3]);
		int of = max(0, ind - rr - gg - yy);
		ans = min(ans, f(r, g, y - 1, 1) + of);
		ans = min(ans, f(r, g, y - 1, 2) + of);
		// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
	}
	// cout << r << " " << g << " " << y << " " << lst << " = " <<  ans << endl;
	return ans;
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	h['R'] = 1;
	h['G'] = 2;
	h['Y'] = 3;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		char x;
		scanf(" %c",&x);
		a[i] = h[x];	
		say[a[i]]++;
		yer[a[i]][say[a[i]]] = i;
		for(int j = 1; j <= 3; j++)
			pre[i][j] = pre[i - 1][j] + (a[i] == j);
	}
	ans = min(min(f(say[1], say[2], say[3], 1), f(say[1], say[2], say[3], 2)), f(say[1], say[2], say[3], 3));
	if(ans >= inf)
		printf("-1\n");
	else
		printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 7 ms 5668 KB Output is correct
3 Correct 7 ms 5752 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5624 KB Output is correct
6 Correct 6 ms 5628 KB Output is correct
7 Correct 7 ms 5752 KB Output is correct
8 Correct 6 ms 5724 KB Output is correct
9 Correct 6 ms 5624 KB Output is correct
10 Correct 6 ms 5624 KB Output is correct
11 Correct 6 ms 5624 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct
13 Correct 6 ms 5624 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 7 ms 5752 KB Output is correct
16 Correct 6 ms 5624 KB Output is correct
17 Correct 6 ms 5752 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 7 ms 5668 KB Output is correct
3 Correct 7 ms 5752 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5624 KB Output is correct
6 Correct 6 ms 5628 KB Output is correct
7 Correct 7 ms 5752 KB Output is correct
8 Correct 6 ms 5724 KB Output is correct
9 Correct 6 ms 5624 KB Output is correct
10 Correct 6 ms 5624 KB Output is correct
11 Correct 6 ms 5624 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct
13 Correct 6 ms 5624 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 7 ms 5752 KB Output is correct
16 Correct 6 ms 5624 KB Output is correct
17 Correct 6 ms 5752 KB Output is correct
18 Correct 7 ms 5752 KB Output is correct
19 Correct 7 ms 5624 KB Output is correct
20 Correct 7 ms 5624 KB Output is correct
21 Correct 7 ms 5624 KB Output is correct
22 Correct 7 ms 5752 KB Output is correct
23 Correct 7 ms 5624 KB Output is correct
24 Correct 7 ms 5752 KB Output is correct
25 Correct 7 ms 5752 KB Output is correct
26 Correct 7 ms 5752 KB Output is correct
27 Correct 7 ms 5624 KB Output is correct
28 Correct 7 ms 5624 KB Output is correct
29 Correct 7 ms 5752 KB Output is correct
30 Correct 7 ms 5756 KB Output is correct
31 Correct 8 ms 5752 KB Output is correct
32 Correct 9 ms 5752 KB Output is correct
33 Correct 8 ms 5752 KB Output is correct
34 Correct 8 ms 5624 KB Output is correct
35 Correct 7 ms 5752 KB Output is correct
36 Correct 7 ms 5624 KB Output is correct
37 Correct 7 ms 5684 KB Output is correct
38 Correct 7 ms 5736 KB Output is correct
39 Correct 7 ms 5628 KB Output is correct
40 Correct 7 ms 5624 KB Output is correct
41 Correct 6 ms 5752 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Runtime error 14 ms 11256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 7 ms 5668 KB Output is correct
3 Correct 7 ms 5752 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5624 KB Output is correct
6 Correct 6 ms 5628 KB Output is correct
7 Correct 7 ms 5752 KB Output is correct
8 Correct 6 ms 5724 KB Output is correct
9 Correct 6 ms 5624 KB Output is correct
10 Correct 6 ms 5624 KB Output is correct
11 Correct 6 ms 5624 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct
13 Correct 6 ms 5624 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 7 ms 5752 KB Output is correct
16 Correct 6 ms 5624 KB Output is correct
17 Correct 6 ms 5752 KB Output is correct
18 Correct 7 ms 5752 KB Output is correct
19 Correct 7 ms 5624 KB Output is correct
20 Correct 7 ms 5624 KB Output is correct
21 Correct 7 ms 5624 KB Output is correct
22 Correct 7 ms 5752 KB Output is correct
23 Correct 7 ms 5624 KB Output is correct
24 Correct 7 ms 5752 KB Output is correct
25 Correct 7 ms 5752 KB Output is correct
26 Correct 7 ms 5752 KB Output is correct
27 Correct 7 ms 5624 KB Output is correct
28 Correct 7 ms 5624 KB Output is correct
29 Correct 7 ms 5752 KB Output is correct
30 Correct 7 ms 5756 KB Output is correct
31 Correct 8 ms 5752 KB Output is correct
32 Correct 9 ms 5752 KB Output is correct
33 Correct 8 ms 5752 KB Output is correct
34 Correct 8 ms 5624 KB Output is correct
35 Correct 7 ms 5752 KB Output is correct
36 Correct 7 ms 5624 KB Output is correct
37 Correct 7 ms 5684 KB Output is correct
38 Correct 7 ms 5736 KB Output is correct
39 Correct 7 ms 5628 KB Output is correct
40 Correct 7 ms 5624 KB Output is correct
41 Correct 6 ms 5752 KB Output is correct
42 Correct 6 ms 5624 KB Output is correct
43 Runtime error 14 ms 11256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -