oj.uz

Submission #909748

# Submission time Handle Problem Language Result Execution time Memory
909748 2024-01-17T11:42:46 Z OAleksa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 100 ms 307084 KB 
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 410;
const int inf = 1e9 + 69;
int dp[N][N][N][3], n;
string s;
vector<int> pos[3];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> s;
  	int a = 0, b = 0, c = 0;
  	for (int i = 0;i < n;i++) {
  		if (s[i] == 'R')
  			s[i] = 'A';
  		else if (s[i] == 'G')
  			s[i] = 'B';
  		else
  			s[i] = 'C';
  		a += (s[i] == 'A');
  		b += (s[i] == 'B');
  		c += (s[i] == 'C');
  		pos[s[i] - 'A'].push_back(i);
  	}
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++)
  				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
  		}
  	}
  	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++) {
  				int p = i + j + k - 1;
  				if (i > 0) {
  					dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(pos[0][i - 1] - p);
  				}
  				if (j > 0) {
  					dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(pos[1][j - 1] - p);
  				}
  				if (k > 0) {
  					dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]) + abs(pos[2][k - 1] - p);
  				}
  			}
  		}
  	}
  	int ans = inf;
  	for (int i = 0;i < 3;i++)
  		ans = min(ans, dp[a][b][c][i]);
  	if (ans >= inf)	
  		ans = -2;
  	cout << ans / 2;
	}
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2512 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 1 ms 6496 KB Output is correct
5 Correct 2 ms 10708 KB Output is correct
6 Correct 2 ms 12640 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 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 10588 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 2512 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 1 ms 6496 KB Output is correct
5 Correct 2 ms 10708 KB Output is correct
6 Correct 2 ms 12640 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 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 10588 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 4444 KB Output is correct
2 Correct 100 ms 303708 KB Output is correct
3 Correct 98 ms 303376 KB Output is correct
4 Correct 78 ms 305752 KB Output is correct
5 Correct 81 ms 304340 KB Output is correct
6 Correct 80 ms 304100 KB Output is correct
7 Correct 85 ms 303148 KB Output is correct
8 Correct 80 ms 303184 KB Output is correct
9 Correct 80 ms 299352 KB Output is correct
10 Correct 78 ms 303960 KB Output is correct
11 Correct 79 ms 303960 KB Output is correct
12 Correct 33 ms 196696 KB Output is correct
13 Correct 44 ms 224604 KB Output is correct
14 Correct 57 ms 259796 KB Output is correct
15 Correct 78 ms 307040 KB Output is correct
16 Correct 83 ms 307084 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2512 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 1 ms 6496 KB Output is correct
5 Correct 2 ms 10708 KB Output is correct
6 Correct 2 ms 12640 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 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 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -