oj.uz

Submission #532862

# Submission time Handle Problem Language Result Execution time Memory
532862 2022-03-04T06:11:30 Z amunduzbaev Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048580 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 405;
int dp[N][N][N][3];
vector<int> in[3];
int pos[3][N][3];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	ar<int, 3> sz {};
	for(int i=0;i<n;i++){
		if(s[i] == 'R') in[0].push_back(i), sz[0]++;
		if(s[i] == 'G') in[1].push_back(i), sz[1]++;
		if(s[i] == 'Y') in[2].push_back(i), sz[2]++;
	}
	
	for(int t=0;t<3;t++){
		for(int i=0;i<sz[t];i++){
			for(int k=0;k<3;k++){
				for(int j=0;j<sz[k];j++){
					if(in[k][j] > in[t][i]) break;
					pos[t][i][k]++;
				}
			}
		}
	}
	
	memset(dp, 127, sizeof dp);
	dp[0][0][0][0] = 
	dp[0][0][0][1] = 
	dp[0][0][0][2] = 0;
	
	for(int i=0;i<=sz[0];i++){
		for(int j=0;j<=sz[1];j++){
			for(int l=0;l<=sz[2];l++){
				if(i < sz[0]){
					int cc = max(0ll, pos[0][i][1] - j) + max(0ll, pos[0][i][2] - l);
					dp[i+1][j][l][0] = min(dp[i+1][j][l][0], dp[i][j][l][1] + cc);
					dp[i+1][j][l][0] = min(dp[i+1][j][l][0], dp[i][j][l][2] + cc);
				} if(j < sz[1]){
					int cc = max(0ll, pos[1][j][0] - i) + max(0ll, pos[1][j][2] - l);
					dp[i][j+1][l][1] = min(dp[i][j+1][l][1], dp[i][j][l][0] + cc);
					dp[i][j+1][l][1] = min(dp[i][j+1][l][1], dp[i][j][l][2] + cc);
				} if(l < sz[2]){
					int cc = max(0ll, pos[2][l][0] - i) + max(0ll, pos[2][l][1] - j);
					dp[i][j][l+1][2] = min(dp[i][j][l+1][2], dp[i][j][l][0] + cc);
					dp[i][j][l+1][2] = min(dp[i][j][l+1][2], dp[i][j][l][1] + cc);
				}
			}
		}
	}
	
	int res = 1e9;
	for(int i=0;i<3;i++) res = min(res, dp[sz[0]][sz[1]][sz[2]][i]);
	if(res < 1e9) cout<<res<<"\n";
	else cout<<-1<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 519 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 519 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 444 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 519 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -