oj.uz

답안 #960266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960266 2024-04-10T05:45:53 Z LCJLY Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
60 / 100
 5 ms 24668 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,6>pi2;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string s;
vector<int>v[3];
int arr[100];

int memo2[3][100];
int f(int color, int pos){
	if(memo2[color][pos]!=-1) return memo2[color][pos];
	int hold=lower_bound(v[color].begin(),v[color].end(),pos)-v[color].begin();
	return memo2[color][pos]=hold;	
}

int add(int a, int b){
	return  max(0LL,a+b);	
}

int memo[101][101][101][3];

int dp(int r, int g, int b,int last){
	int index=r+g+b;
	if(index==n) return 0;
	if(memo[r][g][b][last]!=-1) return memo[r][g][b][last];
	int ans=1e15;
	
	if(index==0){
		//put red
		if(r<(int)v[0].size())ans=min(ans,dp(r+1,g,b,0)+v[0][r]);
		
		//put green
		if(g<(int)v[1].size())ans=min(ans,dp(r,g+1,b,1)+v[1][g]);
		
		//put blue
		if(g<(int)v[2].size())ans=min(ans,dp(r,g,b+1,2)+v[2][b]);
	}
	else{
		//put red
		if(r<(int)v[0].size() && last!=0){
			int hold=f(1,v[0][r]);
			int hold2=f(2,v[0][r]);
			
			int cost=add(hold,-g)+add(hold2,-b);
			
			ans=min(ans,dp(r+1,g,b,0)+cost);
		}
		
		//put green
		if(g<(int)v[1].size() && last!=1){
			int hold=f(0,v[1][g]);
			int hold2=f(2,v[1][g]);
			
			int cost=add(hold,-r)+add(hold2,-b);
			
			ans=min(ans,dp(r,g+1,b,1)+cost);
		}
		
		//put blue
		if(b<(int)v[2].size() && last!=2){
			int hold=f(0,v[2][b]);
			int hold2=f(1,v[2][b]);
			
			int cost=add(hold,-r)+add(hold2,-g);
			
			ans=min(ans,dp(r,g,b+1,2)+cost);
		}
	}
	return memo[r][g][b][last]=ans;
}

void solve(){
	cin >> n >> s;
	
	for(int x=0;x<n;x++){
		if(s[x]=='R'){
			arr[x]=0;
		}
		else if(s[x]=='G'){
			arr[x]=1;
		}
		else arr[x]=2;
		v[arr[x]].push_back(x);
	}
	
	memset(memo,-1,sizeof(memo));
	memset(memo2,-1,sizeof(memo2));
	int hold=dp(0,0,0,0);
	if(hold>=1e10){
		cout << -1;
	}
	else cout << hold;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24408 KB Output is correct
2 Correct 4 ms 24412 KB Output is correct
3 Correct 4 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 4 ms 24412 KB Output is correct
6 Correct 4 ms 24460 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 4 ms 24412 KB Output is correct
9 Correct 4 ms 24408 KB Output is correct
10 Correct 5 ms 24604 KB Output is correct
11 Correct 4 ms 24412 KB Output is correct
12 Correct 4 ms 24412 KB Output is correct
13 Correct 4 ms 24412 KB Output is correct
14 Correct 4 ms 24412 KB Output is correct
15 Correct 4 ms 24408 KB Output is correct
16 Correct 4 ms 24412 KB Output is correct
17 Correct 4 ms 24408 KB Output is correct
18 Correct 5 ms 24408 KB Output is correct
19 Correct 4 ms 24412 KB Output is correct
20 Correct 4 ms 24452 KB Output is correct
21 Correct 4 ms 24412 KB Output is correct
22 Correct 4 ms 24472 KB Output is correct
23 Correct 5 ms 24668 KB Output is correct
24 Correct 4 ms 24412 KB Output is correct
25 Correct 4 ms 24412 KB Output is correct
26 Correct 4 ms 24408 KB Output is correct
27 Correct 5 ms 24412 KB Output is correct
28 Correct 4 ms 24412 KB Output is correct
29 Correct 4 ms 24456 KB Output is correct
30 Correct 4 ms 24412 KB Output is correct
31 Correct 4 ms 24412 KB Output is correct
32 Correct 4 ms 24408 KB Output is correct
33 Correct 4 ms 24412 KB Output is correct
34 Correct 4 ms 24648 KB Output is correct
35 Correct 4 ms 24412 KB Output is correct
36 Correct 4 ms 24408 KB Output is correct
37 Correct 5 ms 24412 KB Output is correct
38 Correct 4 ms 24412 KB Output is correct
39 Correct 4 ms 24412 KB Output is correct
40 Correct 4 ms 24412 KB Output is correct
41 Correct 5 ms 24488 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24412 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24408 KB Output is correct
2 Correct 4 ms 24412 KB Output is correct
3 Correct 4 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 4 ms 24412 KB Output is correct
6 Correct 4 ms 24460 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 4 ms 24412 KB Output is correct
9 Correct 4 ms 24408 KB Output is correct
10 Correct 5 ms 24604 KB Output is correct
11 Correct 4 ms 24412 KB Output is correct
12 Correct 4 ms 24412 KB Output is correct
13 Correct 4 ms 24412 KB Output is correct
14 Correct 4 ms 24412 KB Output is correct
15 Correct 4 ms 24408 KB Output is correct
16 Correct 4 ms 24412 KB Output is correct
17 Correct 4 ms 24408 KB Output is correct
18 Correct 5 ms 24408 KB Output is correct
19 Correct 4 ms 24412 KB Output is correct
20 Correct 4 ms 24452 KB Output is correct
21 Correct 4 ms 24412 KB Output is correct
22 Correct 4 ms 24472 KB Output is correct
23 Correct 5 ms 24668 KB Output is correct
24 Correct 4 ms 24412 KB Output is correct
25 Correct 4 ms 24412 KB Output is correct
26 Correct 4 ms 24408 KB Output is correct
27 Correct 5 ms 24412 KB Output is correct
28 Correct 4 ms 24412 KB Output is correct
29 Correct 4 ms 24456 KB Output is correct
30 Correct 4 ms 24412 KB Output is correct
31 Correct 4 ms 24412 KB Output is correct
32 Correct 4 ms 24408 KB Output is correct
33 Correct 4 ms 24412 KB Output is correct
34 Correct 4 ms 24648 KB Output is correct
35 Correct 4 ms 24412 KB Output is correct
36 Correct 4 ms 24408 KB Output is correct
37 Correct 5 ms 24412 KB Output is correct
38 Correct 4 ms 24412 KB Output is correct
39 Correct 4 ms 24412 KB Output is correct
40 Correct 4 ms 24412 KB Output is correct
41 Correct 5 ms 24488 KB Output is correct
42 Correct 4 ms 24412 KB Output is correct
43 Runtime error 1 ms 604 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -