oj.uz

Submission #494737

# Submission time Handle Problem Language Result Execution time Memory
494737 2021-12-16T04:39:13 Z Haruto810198 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 10 ms 6976 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 410;

int n;
char arr[MAX];
int R, G, Y;
int rp[MAX], gp[MAX], yp[MAX];
vector<vector<vector<vi>>> dp;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[i];
		if(arr[i] == 'R') rp[++R] = i;
		if(arr[i] == 'G') gp[++G] = i;
		if(arr[i] == 'Y') yp[++Y] = i;
	}

	if(max({R, G, Y}) > (n + 1) / 2){
		cout<<-1<<'\n';
		return 0;
	}
	
	dp.resize(3);
	for(auto& i : dp){
		i.resize(R+1);
		for(auto& j : i){
			j.resize(G+1);
			for(auto& k : j){
				k.resize(Y+1);
				for(int& l : k){
					l = INF;
				}
			}
		}
	}

	dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
	
	FOR(i, 0, R, 1){
		FOR(j, 0, G, 1){
			FOR(k, 0, Y, 1){
				
				int pos = i + j + k;
				int dr = abs(rp[i] - pos);
				int dg = abs(gp[j] - pos);
				int dy = abs(yp[k] - pos);

				if(i > 0){
					dp[0][i][j][k] = min({dp[0][i][j][k], dp[1][i-1][j][k] + dr, dp[2][i-1][j][k] + dr});
				}

				if(j > 0){
					dp[1][i][j][k] = min({dp[1][i][j][k], dp[0][i][j-1][k] + dg, dp[2][i][j-1][k] + dg});
				}

				if(k > 0){
					dp[2][i][j][k] = min({dp[2][i][j][k], dp[0][i][j][k-1] + dy, dp[1][i][j][k-1] + dy});
				}

			}
		}
	}

	int res = min({dp[0][R][G][Y], dp[1][R][G][Y], dp[2][R][G][Y]}) / 2;
	cout<<res<<'\n';

	return 0;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 7 ms 6864 KB Output is correct
3 Correct 10 ms 6864 KB Output is correct
4 Correct 8 ms 6952 KB Output is correct
5 Correct 8 ms 6976 KB Output is correct
6 Correct 8 ms 6864 KB Output is correct
7 Correct 9 ms 6904 KB Output is correct
8 Correct 9 ms 6868 KB Output is correct
9 Correct 8 ms 6864 KB Output is correct
10 Correct 8 ms 6864 KB Output is correct
11 Correct 8 ms 6940 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 5 ms 3388 KB Output is correct
14 Correct 6 ms 4828 KB Output is correct
15 Correct 0 ms 220 KB Output is correct
16 Correct 0 ms 220 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -