답안 #246441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246441	2020-07-09T10:26:14 Z	groeneprof	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	500 ms	109692 KB

joi2019_ho_t3

#include <bits/stdc++.h>
//#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair

using namespace std;
const bool debug = 0;
const int inf = 1e9;
int n;
vector<int> color;
vector<int> pos[3];
int dp[400][400][400][3];
bool vis[400][400][400][3];
int ft[401];

void u(int i, int v){
	for(int j = i; j<=n; j+=(j&-j)){
		ft[j]+=v;
	}
}

void update(int i, int j, int v){
	u(i+1, v); 
	u(j+1, -v);
}

int query(int i){
	int res = 0;
	for(int j = i+1; j>0; j-=(j&-j)){
		res += ft[j];
	}
	return res;

}


int solve(int a[3], int last){
	int g = a[0], y = a[1], r = a[2];
	H(g); H(y); H(r); H(last);
	int j = g + y + r;
	if(vis[g][y][r][last]){
		P("visited, return: "<<dp[g][y][r][last]);
		return dp[g][y][r][last];
	}
	if(g+y+r==n){
		P("reached end");
		return 0;
	}
	vis[g][y][r][last] = 1;
	dp[g][y][r][last] = inf;
	for(int i = 0; i<3; i++) if(i!=last && a[i] < pos[i].size()){
		H(i);
		int extra = pos[i][a[i]] + query(pos[i][a[i]]) - j;
		update(0,pos[i][a[i]],1);
		a[i] ++;
		dp[g][y][r][last] = min(dp[g][y][r][last], solve(a,i)+extra);
		P("a");
		a[i] --;
		P("b");
	
		update(0,pos[i][a[i]],-1);
		
		P("c");

	}
	P("d");
	P(g<<" "<<y<<" "<<r<<" "<<last<<" returns "<< dp[g][y][r][last]);
	return dp[g][y][r][last];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	map<char,int> mp;
	color.resize(n);
	mp['G'] = 0;
	mp['Y'] = 1;
	mp['R'] = 2;
	for(int i = 0; i<n; i++){
		char c;
		cin>>c;
		color[i] = mp[c];
		pos[mp[c]].push_back(i);
	}
	int a[] = {0,0,0};
	int ans = min(solve(a,0),solve(a,1));
	if(ans < 1e6){
		cout<<ans<<endl;
	}
	else{
		cout<<-1<<endl;
	}
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int solve(int*, int)':
joi2019_ho_t3.cpp:62:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<3; i++) if(i!=last && a[i] < pos[i].size()){
                                         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	512 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	5 ms	640 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	5 ms	512 KB	Output is correct
14	Correct	5 ms	512 KB	Output is correct
15	Correct	5 ms	512 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	512 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	5 ms	640 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	5 ms	512 KB	Output is correct
14	Correct	5 ms	512 KB	Output is correct
15	Correct	5 ms	512 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	7 ms	2432 KB	Output is correct
19	Correct	7 ms	2816 KB	Output is correct
20	Correct	7 ms	2304 KB	Output is correct
21	Correct	7 ms	2816 KB	Output is correct
22	Correct	6 ms	2048 KB	Output is correct
23	Correct	7 ms	3072 KB	Output is correct
24	Correct	6 ms	2944 KB	Output is correct
25	Correct	5 ms	768 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	6 ms	2176 KB	Output is correct
28	Correct	7 ms	2688 KB	Output is correct
29	Correct	7 ms	2560 KB	Output is correct
30	Correct	7 ms	3072 KB	Output is correct
31	Correct	7 ms	3200 KB	Output is correct
32	Correct	7 ms	2944 KB	Output is correct
33	Correct	5 ms	1024 KB	Output is correct
34	Correct	5 ms	1280 KB	Output is correct
35	Correct	7 ms	2304 KB	Output is correct
36	Correct	7 ms	2560 KB	Output is correct
37	Correct	7 ms	2944 KB	Output is correct
38	Correct	7 ms	3072 KB	Output is correct
39	Correct	7 ms	2944 KB	Output is correct
40	Correct	5 ms	768 KB	Output is correct
41	Correct	5 ms	1024 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	6 ms	2944 KB	Output is correct
3	Correct	6 ms	2944 KB	Output is correct
4	Correct	6 ms	2976 KB	Output is correct
5	Correct	8 ms	2944 KB	Output is correct
6	Correct	6 ms	2944 KB	Output is correct
7	Correct	6 ms	2944 KB	Output is correct
8	Correct	6 ms	2944 KB	Output is correct
9	Correct	6 ms	2944 KB	Output is correct
10	Correct	7 ms	2944 KB	Output is correct
11	Correct	6 ms	2944 KB	Output is correct
12	Correct	6 ms	1664 KB	Output is correct
13	Correct	6 ms	2048 KB	Output is correct
14	Correct	6 ms	2432 KB	Output is correct
15	Correct	6 ms	2944 KB	Output is correct
16	Correct	6 ms	2944 KB	Output is correct

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	512 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	5 ms	640 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	5 ms	512 KB	Output is correct
14	Correct	5 ms	512 KB	Output is correct
15	Correct	5 ms	512 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	7 ms	2432 KB	Output is correct
19	Correct	7 ms	2816 KB	Output is correct
20	Correct	7 ms	2304 KB	Output is correct
21	Correct	7 ms	2816 KB	Output is correct
22	Correct	6 ms	2048 KB	Output is correct
23	Correct	7 ms	3072 KB	Output is correct
24	Correct	6 ms	2944 KB	Output is correct
25	Correct	5 ms	768 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	6 ms	2176 KB	Output is correct
28	Correct	7 ms	2688 KB	Output is correct
29	Correct	7 ms	2560 KB	Output is correct
30	Correct	7 ms	3072 KB	Output is correct
31	Correct	7 ms	3200 KB	Output is correct
32	Correct	7 ms	2944 KB	Output is correct
33	Correct	5 ms	1024 KB	Output is correct
34	Correct	5 ms	1280 KB	Output is correct
35	Correct	7 ms	2304 KB	Output is correct
36	Correct	7 ms	2560 KB	Output is correct
37	Correct	7 ms	2944 KB	Output is correct
38	Correct	7 ms	3072 KB	Output is correct
39	Correct	7 ms	2944 KB	Output is correct
40	Correct	5 ms	768 KB	Output is correct
41	Correct	5 ms	1024 KB	Output is correct
42	Correct	5 ms	384 KB	Output is correct
43	Correct	6 ms	2944 KB	Output is correct
44	Correct	6 ms	2944 KB	Output is correct
45	Correct	6 ms	2976 KB	Output is correct
46	Correct	8 ms	2944 KB	Output is correct
47	Correct	6 ms	2944 KB	Output is correct
48	Correct	6 ms	2944 KB	Output is correct
49	Correct	6 ms	2944 KB	Output is correct
50	Correct	6 ms	2944 KB	Output is correct
51	Correct	7 ms	2944 KB	Output is correct
52	Correct	6 ms	2944 KB	Output is correct
53	Correct	6 ms	1664 KB	Output is correct
54	Correct	6 ms	2048 KB	Output is correct
55	Correct	6 ms	2432 KB	Output is correct
56	Correct	6 ms	2944 KB	Output is correct
57	Correct	6 ms	2944 KB	Output is correct
58	Execution timed out	566 ms	109692 KB	Time limit exceeded
59	Halted	0 ms	0 KB	-

답안 #246441

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 25.0