oj.uz

Submission #120155

# Submission time Handle Problem Language Result Execution time Memory
120155 2019-06-23T15:15:50 Z antimirage Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 322 ms 355084 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 Correct 268 ms 355084 KB Output is correct
2 Correct 253 ms 354936 KB Output is correct
3 Correct 261 ms 355064 KB Output is correct
4 Correct 258 ms 354856 KB Output is correct
5 Incorrect 257 ms 355032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 355084 KB Output is correct
2 Correct 253 ms 354936 KB Output is correct
3 Correct 261 ms 355064 KB Output is correct
4 Correct 258 ms 354856 KB Output is correct
5 Incorrect 257 ms 355032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 354936 KB Output is correct
2 Correct 267 ms 354912 KB Output is correct
3 Correct 266 ms 354948 KB Output is correct
4 Correct 274 ms 354968 KB Output is correct
5 Correct 279 ms 354932 KB Output is correct
6 Correct 322 ms 354936 KB Output is correct
7 Correct 279 ms 354988 KB Output is correct
8 Correct 278 ms 354852 KB Output is correct
9 Correct 271 ms 354944 KB Output is correct
10 Correct 276 ms 354956 KB Output is correct
11 Correct 288 ms 354932 KB Output is correct
12 Correct 280 ms 354884 KB Output is correct
13 Correct 268 ms 354872 KB Output is correct
14 Correct 277 ms 354944 KB Output is correct
15 Correct 265 ms 354852 KB Output is correct
16 Correct 278 ms 354904 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 355084 KB Output is correct
2 Correct 253 ms 354936 KB Output is correct
3 Correct 261 ms 355064 KB Output is correct
4 Correct 258 ms 354856 KB Output is correct
5 Incorrect 257 ms 355032 KB Output isn't correct
6 Halted 0 ms 0 KB -