oj.uz

Submission #236675

# Submission time Handle Problem Language Result Execution time Memory
236675 2020-06-02T19:34:27 Z _7_7_ Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
75 / 100
 500 ms 815800 KB 
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
	
int n, cnt[N][3], dp[N][N][N][3];
vi pos[3];
string s;


int get (int l, int r, int i) {
	if (l > r)
		return 0;
	return cnt[r][i] - cnt[l - 1][i];
}

int rec (vi c, int lst) {
//	cerr << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << lst << endl;
	if (c[0] + c[1] + c[2] == 0)
		return 0;

	if (!c[lst])
		return inf;

	int &res = dp[c[0]][c[1]][c[2]][lst];
	if (res != -1)
		return res;

	c[lst]--;	
	res = inf;

	int cost = 0;
	for (int j = 0; j < 3; ++j)
		if (j != lst && c[j])
			cost += get(pos[lst][c[lst]], pos[j][c[j] - 1], j);

	for (int j = 0; j < 3; ++j)
		if (j != lst)
			res = min(res, rec(c, j) + cost);
	return res;
	
	
}
	

main () {
	cin >> n >> s;
	s = "#" + s;
	
	memset(dp, -1, sizeof(dp));

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j)
			cnt[i][j] = cnt[i - 1][j];
		if (s[i] == 'R') {
			++cnt[i][0]; 
			pos[0].pb(i);
		} else if (s[i] == 'Y') {
			++cnt[i][1]; 
			pos[1].pb(i);
		} else {
			++cnt[i][2]; 
			pos[2].pb(i);
		}
	}

	vi c;
	for (int j = 0; j < 3; ++j)
		c.pb(cnt[n][j]);

	int ans = min({rec(c, 0), rec(c, 1), rec(c, 2)});	

	if (ans == inf)
		ans = -1;

	cout << ans << endl;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 815732 KB Output is correct
2 Correct 398 ms 815484 KB Output is correct
3 Correct 391 ms 815516 KB Output is correct
4 Correct 399 ms 815484 KB Output is correct
5 Correct 397 ms 815484 KB Output is correct
6 Correct 395 ms 815456 KB Output is correct
7 Correct 394 ms 815560 KB Output is correct
8 Correct 399 ms 815480 KB Output is correct
9 Correct 388 ms 815456 KB Output is correct
10 Correct 404 ms 815480 KB Output is correct
11 Correct 389 ms 815456 KB Output is correct
12 Correct 402 ms 815480 KB Output is correct
13 Correct 396 ms 815476 KB Output is correct
14 Correct 403 ms 815456 KB Output is correct
15 Correct 400 ms 815572 KB Output is correct
16 Correct 396 ms 815480 KB Output is correct
17 Correct 404 ms 815672 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 815732 KB Output is correct
2 Correct 398 ms 815484 KB Output is correct
3 Correct 391 ms 815516 KB Output is correct
4 Correct 399 ms 815484 KB Output is correct
5 Correct 397 ms 815484 KB Output is correct
6 Correct 395 ms 815456 KB Output is correct
7 Correct 394 ms 815560 KB Output is correct
8 Correct 399 ms 815480 KB Output is correct
9 Correct 388 ms 815456 KB Output is correct
10 Correct 404 ms 815480 KB Output is correct
11 Correct 389 ms 815456 KB Output is correct
12 Correct 402 ms 815480 KB Output is correct
13 Correct 396 ms 815476 KB Output is correct
14 Correct 403 ms 815456 KB Output is correct
15 Correct 400 ms 815572 KB Output is correct
16 Correct 396 ms 815480 KB Output is correct
17 Correct 404 ms 815672 KB Output is correct
18 Correct 397 ms 815484 KB Output is correct
19 Correct 395 ms 815480 KB Output is correct
20 Correct 396 ms 815632 KB Output is correct
21 Correct 398 ms 815480 KB Output is correct
22 Correct 404 ms 815480 KB Output is correct
23 Correct 401 ms 815480 KB Output is correct
24 Correct 399 ms 815440 KB Output is correct
25 Correct 402 ms 815480 KB Output is correct
26 Correct 393 ms 815564 KB Output is correct
27 Correct 400 ms 815608 KB Output is correct
28 Correct 399 ms 815456 KB Output is correct
29 Correct 399 ms 815608 KB Output is correct
30 Correct 398 ms 815608 KB Output is correct
31 Correct 405 ms 815480 KB Output is correct
32 Correct 404 ms 815608 KB Output is correct
33 Correct 395 ms 815504 KB Output is correct
34 Correct 404 ms 815532 KB Output is correct
35 Correct 397 ms 815568 KB Output is correct
36 Correct 403 ms 815608 KB Output is correct
37 Correct 397 ms 815608 KB Output is correct
38 Correct 398 ms 815556 KB Output is correct
39 Correct 396 ms 815608 KB Output is correct
40 Correct 400 ms 815528 KB Output is correct
41 Correct 398 ms 815608 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 815476 KB Output is correct
2 Correct 398 ms 815800 KB Output is correct
3 Correct 403 ms 815532 KB Output is correct
4 Correct 396 ms 815608 KB Output is correct
5 Correct 394 ms 815684 KB Output is correct
6 Correct 408 ms 815608 KB Output is correct
7 Correct 395 ms 815580 KB Output is correct
8 Correct 392 ms 815608 KB Output is correct
9 Correct 399 ms 815608 KB Output is correct
10 Correct 398 ms 815608 KB Output is correct
11 Correct 399 ms 815548 KB Output is correct
12 Correct 396 ms 815584 KB Output is correct
13 Correct 399 ms 815480 KB Output is correct
14 Correct 392 ms 815480 KB Output is correct
15 Correct 399 ms 815608 KB Output is correct
16 Correct 402 ms 815564 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 815732 KB Output is correct
2 Correct 398 ms 815484 KB Output is correct
3 Correct 391 ms 815516 KB Output is correct
4 Correct 399 ms 815484 KB Output is correct
5 Correct 397 ms 815484 KB Output is correct
6 Correct 395 ms 815456 KB Output is correct
7 Correct 394 ms 815560 KB Output is correct
8 Correct 399 ms 815480 KB Output is correct
9 Correct 388 ms 815456 KB Output is correct
10 Correct 404 ms 815480 KB Output is correct
11 Correct 389 ms 815456 KB Output is correct
12 Correct 402 ms 815480 KB Output is correct
13 Correct 396 ms 815476 KB Output is correct
14 Correct 403 ms 815456 KB Output is correct
15 Correct 400 ms 815572 KB Output is correct
16 Correct 396 ms 815480 KB Output is correct
17 Correct 404 ms 815672 KB Output is correct
18 Correct 397 ms 815484 KB Output is correct
19 Correct 395 ms 815480 KB Output is correct
20 Correct 396 ms 815632 KB Output is correct
21 Correct 398 ms 815480 KB Output is correct
22 Correct 404 ms 815480 KB Output is correct
23 Correct 401 ms 815480 KB Output is correct
24 Correct 399 ms 815440 KB Output is correct
25 Correct 402 ms 815480 KB Output is correct
26 Correct 393 ms 815564 KB Output is correct
27 Correct 400 ms 815608 KB Output is correct
28 Correct 399 ms 815456 KB Output is correct
29 Correct 399 ms 815608 KB Output is correct
30 Correct 398 ms 815608 KB Output is correct
31 Correct 405 ms 815480 KB Output is correct
32 Correct 404 ms 815608 KB Output is correct
33 Correct 395 ms 815504 KB Output is correct
34 Correct 404 ms 815532 KB Output is correct
35 Correct 397 ms 815568 KB Output is correct
36 Correct 403 ms 815608 KB Output is correct
37 Correct 397 ms 815608 KB Output is correct
38 Correct 398 ms 815556 KB Output is correct
39 Correct 396 ms 815608 KB Output is correct
40 Correct 400 ms 815528 KB Output is correct
41 Correct 398 ms 815608 KB Output is correct
42 Correct 405 ms 815476 KB Output is correct
43 Correct 398 ms 815800 KB Output is correct
44 Correct 403 ms 815532 KB Output is correct
45 Correct 396 ms 815608 KB Output is correct
46 Correct 394 ms 815684 KB Output is correct
47 Correct 408 ms 815608 KB Output is correct
48 Correct 395 ms 815580 KB Output is correct
49 Correct 392 ms 815608 KB Output is correct
50 Correct 399 ms 815608 KB Output is correct
51 Correct 398 ms 815608 KB Output is correct
52 Correct 399 ms 815548 KB Output is correct
53 Correct 396 ms 815584 KB Output is correct
54 Correct 399 ms 815480 KB Output is correct
55 Correct 392 ms 815480 KB Output is correct
56 Correct 399 ms 815608 KB Output is correct
57 Correct 402 ms 815564 KB Output is correct
58 Execution timed out 759 ms 815736 KB Time limit exceeded
59 Halted 0 ms 0 KB -