oj.uz

Submission #1089445

# Submission time Handle Problem Language Result Execution time Memory
1089445 2024-09-16T14:02:45 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
100 / 100
 311 ms 380884 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back	
#define pob pop_back
#define int long long
#define int2 __int128_t
#define Shrek_Crush228 ios_base::sync_with_stdio(0), cin.tie(0);
#define F first
#define S second
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define sigma signed
#define pii pair <int, int> 

using namespace std;

const int N = 400 + 1;
const int inf = 1e18;

int a[N], b[N], c[N], l, r, n, m, ans, x;
string s, s1;

int posr[N], posg[N], posy[N], pr[N], pg[N], py[N];

void solve()
{
	cin >> n >> s;
	int cntr = 0, cntg = 0, cnty = 0;
	
	FOR( i, 1, n, 1 )
	{
		pr[i] = pr[i - 1], pg[i] = pg[i - 1], py[i] = py[i - 1];
		
		if( s[i - 1] == 'R' ) cntr ++, posr[cntr] = i, pr[i] ++;
		if( s[i - 1] == 'G' ) cntg ++, posg[cntg] = i, pg[i] ++;
		if( s[i - 1] == 'Y' ) cnty ++, posy[cnty] = i, py[i] ++;
	}
	int dp[n + 1][cntr + 1][cntg + 1][3];
	
	FOR( id, 1, n, 1 )
	{
		FOR( R, 0, cntr, 1 )
		{
			FOR( G, 0, cntg, 1 ) dp[id][R][G][0] = inf, dp[id][R][G][1] = inf, dp[id][R][G][2] = inf;
		}
	}
	dp[0][0][0][0] = 0, dp[0][0][0][1] = 0, dp[0][0][0][2] = 0;
	
	FOR( id, 1, n, 1 )
	{
		FOR( R, 0, cntr, 1 )
		{
			if( R > id ) break;
			
			FOR( G, 0, cntg, 1 )
			{
				if( R + G > id ) break;
				
				int Y = id - R - G;
				if( Y > cnty ) continue;
				
				int pos0 = posr[R], cnt0 = max( 0ll, Y - py[pos0] ) + max( 0ll, G - pg[pos0] ), answ0 = max( 0ll, pos0 + cnt0 - id );
				int pos1 = posg[G], cnt1 = max( 0ll, Y - py[pos1] ) + max( 0ll, R - pr[pos1] ), answ1 = max( 0ll, pos1 + cnt1 - id );
				int pos2 = posy[Y], cnt2 = max( 0ll, R - pr[pos2] ) + max( 0ll, G - pg[pos2] ), answ2 = max( 0ll, pos2 + cnt2 - id );
				
				if( R ) dp[id][R][G][0] = min( dp[id - 1][R - 1][G][1], dp[id - 1][R - 1][G][2] ) + answ0;
				if( G ) dp[id][R][G][1] = min( dp[id - 1][R][G - 1][0], dp[id - 1][R][G - 1][2] ) + answ1;
				if( Y ) dp[id][R][G][2] = min( dp[id - 1][R][G][0], dp[id - 1][R][G][1] ) + answ2;
			}
		}
	}
	ans = min({ dp[n][cntr][cntg][0], dp[n][cntr][cntg][1], dp[n][cntr][cntg][2] });
	cout << ( ans >= inf ? -1 : ans );
}
sigma main() 
{
	//freopen("rmq.in", "r", stdin);
	//freopen("rmq.out", "w", stdout);
	    
    Shrek_Crush228	
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 1628 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 976 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1628 KB Output is correct
34 Correct 1 ms 1372 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 856 KB Output is correct
37 Correct 1 ms 860 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 1 ms 1116 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 1116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 206 ms 380780 KB Output is correct
3 Correct 221 ms 377996 KB Output is correct
4 Correct 208 ms 380752 KB Output is correct
5 Correct 210 ms 380700 KB Output is correct
6 Correct 208 ms 380716 KB Output is correct
7 Correct 211 ms 377940 KB Output is correct
8 Correct 202 ms 377940 KB Output is correct
9 Correct 311 ms 375128 KB Output is correct
10 Correct 206 ms 380884 KB Output is correct
11 Correct 223 ms 380712 KB Output is correct
12 Correct 31 ms 52820 KB Output is correct
13 Correct 72 ms 123216 KB Output is correct
14 Correct 127 ms 214608 KB Output is correct
15 Correct 213 ms 380756 KB Output is correct
16 Correct 218 ms 380756 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 1628 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 976 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1628 KB Output is correct
34 Correct 1 ms 1372 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Correct 1 ms 856 KB Output is correct
37 Correct 1 ms 860 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 1 ms 1116 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 1116 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 206 ms 380780 KB Output is correct
44 Correct 221 ms 377996 KB Output is correct
45 Correct 208 ms 380752 KB Output is correct
46 Correct 210 ms 380700 KB Output is correct
47 Correct 208 ms 380716 KB Output is correct
48 Correct 211 ms 377940 KB Output is correct
49 Correct 202 ms 377940 KB Output is correct
50 Correct 311 ms 375128 KB Output is correct
51 Correct 206 ms 380884 KB Output is correct
52 Correct 223 ms 380712 KB Output is correct
53 Correct 31 ms 52820 KB Output is correct
54 Correct 72 ms 123216 KB Output is correct
55 Correct 127 ms 214608 KB Output is correct
56 Correct 213 ms 380756 KB Output is correct
57 Correct 218 ms 380756 KB Output is correct
58 Correct 116 ms 149728 KB Output is correct
59 Correct 140 ms 190028 KB Output is correct
60 Correct 123 ms 171956 KB Output is correct
61 Correct 121 ms 166480 KB Output is correct
62 Correct 203 ms 370772 KB Output is correct
63 Correct 205 ms 365748 KB Output is correct
64 Correct 179 ms 319060 KB Output is correct
65 Correct 168 ms 276820 KB Output is correct
66 Correct 111 ms 168020 KB Output is correct
67 Correct 107 ms 163152 KB Output is correct
68 Correct 113 ms 174180 KB Output is correct
69 Correct 110 ms 168020 KB Output is correct
70 Correct 116 ms 182100 KB Output is correct
71 Correct 107 ms 164432 KB Output is correct
72 Correct 49 ms 79708 KB Output is correct
73 Correct 4 ms 5464 KB Output is correct