oj.uz

Submission #487361

# Submission time Handle Problem Language Result Execution time Memory
487361 2021-11-15T10:21:45 Z PoPularPlusPlus Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
75 / 100
 500 ms 132772 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

//ll dp[401][401][401][3];
vector<vector<vector<vector<int>>>> dp;
vector<int> a , b , c;

ll rec(int i , int j , int k , int col , int s1 , int s2 , int s3){
	if(i == s1 && j == s2 && k == s3)return 0;
	if(dp[i][j][k][col]!=-1)return dp[i][j][k][col];
	if(col == 0){
		if(i == s1)return 1e9;
		int p = upper_bound(all(b) , a[i]) - b.begin();
		p = max(0 , j - p);
		int p1 = upper_bound(all(c) , a[i]) - c.begin();
		p1 = max(0 , k - p1);
		int pos = a[i] + p + p1;
		return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i + 1 , j , k , 1 , s1 , s2 , s3) , rec(i + 1 , j , k , 2 , s1 , s2 , s3));
	}
	if(col == 1){
		if(j == s2)return 1e9;
		int p = upper_bound(all(a) , b[j]) - a.begin();
		p = max(0 , i - p);
		int p1 = upper_bound(all(c) , b[j]) - c.begin();
		p1 = max(0 , k - p1);
		int pos = b[j] + p + p1;
		return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i , j + 1 , k , 0 ,  s1, s2 , s3) , rec(i , j + 1 , k , 2 , s1 , s2 , s3));
	}
	if(k == s3)return 1e9;
	int p = upper_bound(all(a) , c[k]) - a.begin();
	p = max(0 , i - p);
	int p1 = upper_bound(all(b) , c[k]) - b.begin();
	p1 = max(0 , j - p1);
	int pos = c[k] + p + p1;
	return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i , j , k + 1 , 0 ,s1 , s2 ,s3) , rec(i , j , k + 1 , 1 , s1 , s2 , s3));
}

void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0; i < n; i++){
		if(s[i]=='R')a.pb(i);
		else if(s[i] == 'G')b.pb(i);
		else c.pb(i);
	}
	dp.resize(a.size() + 2);
	for(int i = 0; i < (int)a.size() + 1; i++){
		dp[i].resize(b.size() + 2);
		for(int j = 0; j < (int)b.size() + 1; j++){
			dp[i][j].resize(c.size() + 2);
			for(int k = 0; k < (int)c.size() + 1; k++){
				dp[i][j][k].pb(-1);
				dp[i][j][k].pb(-1);
				dp[i][j][k].pb(-1);
			}
		}
	}
	ll ans = min({rec(0,0,0,0,a.size(),b.size(),c.size()),rec(0,0,0,1,a.size(),b.size(),c.size()),rec(0,0,0,2,a.size(),b.size(),c.size())});
	if(ans >= 1e9)ans = -1;
	cout << ans << '\n';
	/*ll dp[a.size() + 1][b.size() + 1][c.size() + 1][3];
	ll ans = 1e9;
	for(int i = 0; i <= (int)a.size() + 1; i++){
		for(int j = 0; j <= (int)b.size() + 1; j++){
			for(int k = 0; k <= (int)c.size() + 1; k++){
				dp[i][j][k][2] = dp[i][j][k][1] = dp[i][j][k][0] = 1e9;
				if(k < (int)c.size()){
					int p = upper_bound(all(a) , c[k]) - a.begin();
					int p1 = upper_bound(all(b) , c[k]) - b.begin();
					int pos = c[k] + p + p1;
					dp[i][j][k][2] = min(dp[i][j][k][2] , abs(pos - (i + j + k)) + min(dp[i][j][k-1][0] , dp[i][j][k-1][1]));
				}
				if(j < (int)b.size()){
					int p = upper_bound(all(a) , b[j]) - a.begin();
					int p1 = upper_bound(all(c) , b[j]) - c.begin();
					int pos = b[j] + p + p1;
					dp[i][j][k][1] = min(dp[i][j][k][1] , abs(pos - (i + j + k)) + min(dp[i][j-1][k][0] , dp[i][j-1][k][2]));
				}
				if(i < (int)a.size()){
					int p = upper_bound(all(b) , a[i]) - b.begin();
					int p1 = upper_bound(all(c) , a[i]) - c.begin();
					int pos = a[i] + p + p1;
					dp[i][j][k][0] = min(dp[i][j][k][0] , abs(pos - (i + j + k)) + min(dp[i-1][j][k][1] , dp[i-1][j][k][2]));
				}
				if(a.size() + b.size() + c.size() == i + j + k + 1){
					ans = min({ans , dp[i][j][k][0] , dp[i][j][k][1] , dp[i][j][k][2]});
				}
			}
		}
	}
	cout << ans << '\n';*/
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 0 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 0 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 720 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 3 ms 720 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 720 KB Output is correct
32 Correct 2 ms 720 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 572 KB Output is correct
35 Correct 1 ms 720 KB Output is correct
36 Correct 2 ms 704 KB Output is correct
37 Correct 2 ms 720 KB Output is correct
38 Correct 2 ms 720 KB Output is correct
39 Correct 2 ms 828 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 464 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 7 ms 5052 KB Output is correct
3 Correct 8 ms 5072 KB Output is correct
4 Correct 12 ms 5072 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 9 ms 5072 KB Output is correct
7 Correct 10 ms 5072 KB Output is correct
8 Correct 8 ms 5072 KB Output is correct
9 Correct 7 ms 5044 KB Output is correct
10 Correct 7 ms 5072 KB Output is correct
11 Correct 8 ms 5004 KB Output is correct
12 Correct 2 ms 1488 KB Output is correct
13 Correct 4 ms 2492 KB Output is correct
14 Correct 5 ms 3536 KB Output is correct
15 Correct 7 ms 5072 KB Output is correct
16 Correct 7 ms 5072 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 0 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 720 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 3 ms 720 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 720 KB Output is correct
32 Correct 2 ms 720 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 572 KB Output is correct
35 Correct 1 ms 720 KB Output is correct
36 Correct 2 ms 704 KB Output is correct
37 Correct 2 ms 720 KB Output is correct
38 Correct 2 ms 720 KB Output is correct
39 Correct 2 ms 828 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 464 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 7 ms 5052 KB Output is correct
44 Correct 8 ms 5072 KB Output is correct
45 Correct 12 ms 5072 KB Output is correct
46 Correct 8 ms 5120 KB Output is correct
47 Correct 9 ms 5072 KB Output is correct
48 Correct 10 ms 5072 KB Output is correct
49 Correct 8 ms 5072 KB Output is correct
50 Correct 7 ms 5044 KB Output is correct
51 Correct 7 ms 5072 KB Output is correct
52 Correct 8 ms 5004 KB Output is correct
53 Correct 2 ms 1488 KB Output is correct
54 Correct 4 ms 2492 KB Output is correct
55 Correct 5 ms 3536 KB Output is correct
56 Correct 7 ms 5072 KB Output is correct
57 Correct 7 ms 5072 KB Output is correct
58 Execution timed out 605 ms 132772 KB Time limit exceeded
59 Halted 0 ms 0 KB -