oj.uz

Submission #1089416

# Submission time Handle Problem Language Result Execution time Memory
1089416 2024-09-16T12:48:59 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 223 ms 381792 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#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 no cout << "NO\n"
#define yes cout << "YES\n"
#define nep next_permutation
#define sigma signed
#define pii pair <int, int> 

using namespace std;

string alp = "abcdefghijklmnopqrstuvwxyz";
string ae = "aoeiuy";
string nums = "123456789";

const int N = 400 + 1;
const int inf = 1e18;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;
const long long maxsum = 1e14;

int a[N], b[N], c[N], l, r, n, m, w, sum, sum1, y, ans1, mx = -inf, mn = inf, ind, ind1, pref[N], suf[N];
string s, s1;
ll ans, x;

template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct RT
{
	int sum, l, r, ind;	
};
int gcd( int a, int b )
{
	return ( b ? gcd( b, a % b ) : a );
}
int lcm( int a, int b )
{
	return a / gcd( a, b ) * b;
}
int bp( int a, int b, int m )
{
	if( !b ) return 1;
	if( b & 1 ) return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m * a % m;
	else return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m;
}
struct po
{
	int mn, sum, mx;
};
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 + 2][cntr + 1][cntg + 1][3];
	
	FOR( id, 0, n, 1 )
	{
		FOR( R, 0, cntr, 1 )
		{
			FOR( G, 0, cntg, 1 ) dp[id][R][G][0] = dp[id][R][G][1] = dp[id][R][G][2] = inf;
		}
	}
	dp[0][0][0][0] = dp[0][0][0][1] = 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 588 KB Output is correct
2 Correct 191 ms 381780 KB Output is correct
3 Correct 196 ms 378956 KB Output is correct
4 Correct 203 ms 381792 KB Output is correct
5 Correct 206 ms 381616 KB Output is correct
6 Correct 209 ms 381776 KB Output is correct
7 Correct 210 ms 378872 KB Output is correct
8 Correct 204 ms 378848 KB Output is correct
9 Correct 202 ms 375944 KB Output is correct
10 Correct 212 ms 381776 KB Output is correct
11 Correct 212 ms 381728 KB Output is correct
12 Correct 32 ms 53076 KB Output is correct
13 Correct 76 ms 123728 KB Output is correct
14 Correct 125 ms 215116 KB Output is correct
15 Correct 223 ms 381592 KB Output is correct
16 Correct 215 ms 381780 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -