oj.uz

답안 #891830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891830 2023-12-24T07:24:42 Z Vvnx Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 51 ms 302420 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 403;
const ll INF = 1e9;

ll n,r,g,b;
string s;
vector<ll> pos[5];
ll dp[N][N][N][3];

int main() {
	cin >> n >> s;
	s = '!' + s;
	for(int i=1; i<=n; i++) {
		if(s[i] == 'R') {
			r++;
			pos[0].pb(i);
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(i);
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(i);
		}
	}
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				for(int l=0; l<=2; l++) dp[i][j][k][l] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1],dp[i-1][j][k][2]) + abs(i+j+k-pos[0][i-1]);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + abs(i+j+k-pos[1][j-1]);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + abs(i+j+k-pos[2][k-1]);
			}
		}
	}
	ll ans = min({dp[r][g][b][0],dp[r][g][b][1],dp[r][g][b][2]});
	if(ans >= INF) cout << -1 << endl;
	else cout << ans/2 << endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Incorrect 2 ms 10748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Incorrect 2 ms 10748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 46 ms 301104 KB Output is correct
3 Correct 50 ms 299788 KB Output is correct
4 Correct 51 ms 300112 KB Output is correct
5 Correct 48 ms 300108 KB Output is correct
6 Correct 46 ms 299860 KB Output is correct
7 Correct 47 ms 301652 KB Output is correct
8 Correct 46 ms 301600 KB Output is correct
9 Correct 46 ms 301184 KB Output is correct
10 Correct 46 ms 302420 KB Output is correct
11 Correct 47 ms 302360 KB Output is correct
12 Correct 20 ms 197464 KB Output is correct
13 Correct 26 ms 247092 KB Output is correct
14 Correct 36 ms 267348 KB Output is correct
15 Correct 47 ms 300772 KB Output is correct
16 Correct 48 ms 299404 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Incorrect 2 ms 10748 KB Output isn't correct
12 Halted 0 ms 0 KB -