oj.uz

Submission #120154

# Submission time Handle Problem Language Result Execution time Memory
120154 2019-06-23T15:12:41 Z antimirage Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 305 ms 355076 KB 
/**
	GOT A FEELING THAT I"M GOING UNDER
**/
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1505;

int n, a[N];

string s;

int dp[N][N][10][4], ans = 1e9 + 7;

void update (int &a, int b) {
	a = b;
}

main(){
	cin >> n >> s;
	s = ' ' + s;
	
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'R')
			a[i] = 1;
		else if (s[i] == 'G')
			a[i] = 2;
	}
	memset( dp, 0x3f3f3f3f, sizeof(dp));
	dp[1][1][1 << a[1]][3] = 0;
	
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= i; j++) {
			for (int mask = 1; mask < 8; mask++) {
				for (int last = 0; last <= 3; last++) {
					
					if ( (mask & (1 << a[i + 1]) ) == 0 ) {
						if (a[i + 1] != last)
							dp[i + 1][j][mask][ a[i + 1] ] = min( dp[i][j][mask][last] + j, dp[i + 1][j][mask][ a[i + 1] ] );
						
						if (j > 1)
							dp[i + 1][j - 1][mask][ a[i + 1] ] = min( dp[i][j][mask][last] + j - 1, dp[i + 1][j - 1][mask][ a[i + 1] ] );
						
						
						if (__builtin_popcount(mask) == 1 && j == 1) {
							for (int l = 0; l < 3; l++) {
								if (mask & (1 << l) ) {
									dp[i + 1][1][1 << a[i + 1]][l] = min( dp[i + 1][1][1 << a[i + 1]][l], dp[i][j][mask][last] );
								}
							}
						}
					}
					dp[i + 1][j + 1][mask | (1 << a[i + 1])][last] = min( dp[i][j][mask][last], dp[i + 1][j + 1][mask | (1 << a[i + 1])][last] );
				}
			}
		}
	}
	for (int i = 0; i < 3; i++) 
		for (int j = 0; j < 3; j++) 
			ans = min(ans, dp[n][1][1 << i][j]);
		
	if (ans == 1e9 + 7) ans = -1;
	
	cout << ans << endl;
}

Compilation message

joi2019_ho_t3.cpp:26:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 355076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 355076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 354852 KB Output is correct
2 Correct 266 ms 354936 KB Output is correct
3 Correct 262 ms 354936 KB Output is correct
4 Correct 267 ms 355064 KB Output is correct
5 Correct 267 ms 354968 KB Output is correct
6 Correct 266 ms 354936 KB Output is correct
7 Correct 262 ms 354936 KB Output is correct
8 Correct 262 ms 354936 KB Output is correct
9 Correct 279 ms 355028 KB Output is correct
10 Correct 269 ms 355072 KB Output is correct
11 Correct 267 ms 355064 KB Output is correct
12 Correct 276 ms 354908 KB Output is correct
13 Correct 259 ms 354936 KB Output is correct
14 Correct 268 ms 354884 KB Output is correct
15 Correct 260 ms 354936 KB Output is correct
16 Correct 261 ms 354936 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 355076 KB Output isn't correct
2 Halted 0 ms 0 KB -