oj.uz

Submission #207093

# Submission time Handle Problem Language Result Execution time Memory
207093 2020-03-06T11:52:51 Z cheissmart Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 774776 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 404;

int dp[N][N][N][3], a[N], cnt[N][3];
vi occ[3];

signed main()
{
	IO_OP;
	
	int n;
	string s;
	cin >> n >> s;
	for(int i=0;i<n;i++) {
		a[i+1] = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
		occ[a[i+1]].PB(i+1);
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<3;j++) cnt[i][j] = cnt[i-1][j];
		cnt[i][a[i]]++;
	}
	memset(dp, 0x3f, sizeof dp);
	for(int i=0;i<=cnt[n][0];i++) {
		for(int j=0;j<=cnt[n][1];j++) {
			for(int k=0;k<=cnt[n][2];k++) {
				if(i == 0 && j == 0 && k == 0) {
					for(int l=0;l<3;l++)
						dp[i][j][k][l] = 0;
				} else {
					for(int l=0;l<3;l++) {
						int pos, jump, pre_dp;
						if(l == 0) {
							if(i == 0) continue;
							pre_dp = min(dp[i-1][j][k][1], dp[i-1][j][k][2]);
							pos = occ[l][i-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - (i-1));
							jump += max(0, cnt[pos-1][1] - j);
							jump += max(0, cnt[pos-1][2] - k);
						} else if(l == 1) {
							if(j == 0) continue;
							pre_dp = min(dp[i][j-1][k][0], dp[i][j-1][k][2]);
							pos = occ[l][j-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - i);
							jump += max(0, cnt[pos-1][1] - (j-1));
							jump += max(0, cnt[pos-1][2] - k);
						} else {
							if(k == 0) continue;
							pre_dp = min(dp[i][j][k-1][0], dp[i][j][k-1][1]);
							pos = occ[l][k-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - i);
							jump += max(0, cnt[pos-1][1] - j);
							jump += max(0, cnt[pos-1][2] - (k-1));
						}
						dp[i][j][k][l] = min(dp[i][j][k][l], pre_dp + jump);
					}
				}
			}
		}
	}
	int ans = INF;
	for(int i=0;i<3;i++)
		ans = min(ans, dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][i]);
	if(ans > 1e8) ans = -1;
	cout << ans << endl;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 556 ms 774684 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 556 ms 774684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 774516 KB Output is correct
2 Correct 423 ms 774520 KB Output is correct
3 Correct 418 ms 774520 KB Output is correct
4 Correct 427 ms 774648 KB Output is correct
5 Correct 419 ms 774648 KB Output is correct
6 Correct 419 ms 774520 KB Output is correct
7 Correct 418 ms 774776 KB Output is correct
8 Correct 409 ms 774648 KB Output is correct
9 Correct 427 ms 774520 KB Output is correct
10 Correct 422 ms 774524 KB Output is correct
11 Correct 415 ms 774648 KB Output is correct
12 Correct 413 ms 774576 KB Output is correct
13 Correct 411 ms 774648 KB Output is correct
14 Correct 418 ms 774520 KB Output is correct
15 Correct 422 ms 774528 KB Output is correct
16 Correct 426 ms 774568 KB Output is correct

Subtask #4
0 / 25.0

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