oj.uz

Submission #865926

# Submission time Handle Problem Language Result Execution time Memory
865926 2023-10-25T03:42:06 Z phoenix0423 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 39 ms 390244 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 400 + 5;
const int INF = 1e9;
int dp[3][maxn][maxn][maxn];

int main(void){
	fastio;
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector<vector<int>> pos(3);
	for(int i = 0; i < n; i++){
		if(s[i] == 'R') pos[0].pb(i);
		else if(s[i] == 'Y') pos[1].pb(i);
		else pos[2].pb(i);
	}
	for(int i = 0; i < 3; i++){
		if(pos[i].size() > (n + 1) / 2){
			cout<<-1<<"\n";
			return 0;
		}
	}
	for(int i = 0; i < 3; i++) for(int j = 0; j <= pos[0].size(); j++) for(int k = 0; k <= pos[1].size(); k++) for(int l = 0; l <= pos[2].size(); l++) dp[i][j][k][l] = INF;
	if(pos[0].size()) dp[0][1][0][0] = pos[0][0];
	if(pos[1].size()) dp[1][0][1][0] = pos[1][0];
	if(pos[2].size()) dp[2][0][0][1] = pos[2][0];
	for(int i = 2; i <= n; i++){
		for(int a = 0; a <= pos[0].size(); a++){
			for(int b = 0; b <= pos[1].size(); b++){
				int c = i - a - b;
				if(c > pos[2].size()) continue;
				for(int lst = 0; lst < 3; lst++) dp[lst][a][b][c] = INF;
				if(a) dp[0][a][b][c] = min(dp[1][a - 1][b][c], dp[2][a - 1][b][c]) + abs(pos[0][a - 1] - (i - 1));
				if(b) dp[1][a][b][c] = min(dp[0][a][b - 1][c], dp[2][a][b - 1][c]) + abs(pos[1][b - 1] - (i - 1));
				if(c) dp[2][a][b][c] = min(dp[0][a][b][c - 1], dp[1][a][b][c - 1]) + abs(pos[2][c - 1] - (i - 1));
			}
		}
	}
	int ans = INF;
	for(int i = 0; i < 3; i++) ans = min(ans, dp[i][pos[0].size()][pos[1].size()][pos[2].size()]);
	cout<<ans / 2<<"\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |   if(pos[i].size() > (n + 1) / 2){
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < 3; i++) for(int j = 0; j <= pos[0].size(); j++) for(int k = 0; k <= pos[1].size(); k++) for(int l = 0; l <= pos[2].size(); l++) dp[i][j][k][l] = INF;
      |                                            ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:86: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < 3; i++) for(int j = 0; j <= pos[0].size(); j++) for(int k = 0; k <= pos[1].size(); k++) for(int l = 0; l <= pos[2].size(); l++) dp[i][j][k][l] = INF;
      |                                                                                    ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:126: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < 3; i++) for(int j = 0; j <= pos[0].size(); j++) for(int k = 0; k <= pos[1].size(); k++) for(int l = 0; l <= pos[2].size(); l++) dp[i][j][k][l] = INF;
      |                                                                                                                            ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int a = 0; a <= pos[0].size(); a++){
      |                  ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int b = 0; b <= pos[1].size(); b++){
      |                   ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if(c > pos[2].size()) continue;
      |        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 16728 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 2 ms 14684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 16728 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 2 ms 14684 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 8536 KB Output is correct
2 Correct 39 ms 390136 KB Output is correct
3 Correct 38 ms 390228 KB Output is correct
4 Correct 36 ms 390228 KB Output is correct
5 Correct 37 ms 390228 KB Output is correct
6 Correct 36 ms 390236 KB Output is correct
7 Correct 39 ms 388180 KB Output is correct
8 Correct 37 ms 388176 KB Output is correct
9 Correct 38 ms 388068 KB Output is correct
10 Correct 38 ms 390228 KB Output is correct
11 Correct 36 ms 390244 KB Output is correct
12 Correct 19 ms 203612 KB Output is correct
13 Correct 26 ms 269148 KB Output is correct
14 Correct 30 ms 322396 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 16728 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 2 ms 14684 KB Output isn't correct
12 Halted 0 ms 0 KB -