oj.uz

Submission #1089409

# Submission time Handle Problem Language Result Execution time Memory
1089409 2024-09-16T12:38:02 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 279 ms 715092 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];
int dp[N][N][N][3];

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] ++;
	}
	FOR( id, 1, 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( cnty < Y ) 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 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 2 ms 23132 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 2 ms 21084 KB Output is correct
9 Correct 2 ms 21084 KB Output is correct
10 Correct 2 ms 23132 KB Output is correct
11 Correct 2 ms 22996 KB Output is correct
12 Correct 2 ms 20984 KB Output is correct
13 Incorrect 2 ms 21084 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 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 2 ms 23132 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 2 ms 21084 KB Output is correct
9 Correct 2 ms 21084 KB Output is correct
10 Correct 2 ms 23132 KB Output is correct
11 Correct 2 ms 22996 KB Output is correct
12 Correct 2 ms 20984 KB Output is correct
13 Incorrect 2 ms 21084 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 1 ms 6492 KB Output is correct
2 Correct 216 ms 714724 KB Output is correct
3 Correct 219 ms 711544 KB Output is correct
4 Correct 212 ms 715052 KB Output is correct
5 Correct 218 ms 714576 KB Output is correct
6 Correct 224 ms 714680 KB Output is correct
7 Correct 213 ms 707152 KB Output is correct
8 Correct 212 ms 709452 KB Output is correct
9 Correct 240 ms 706100 KB Output is correct
10 Correct 228 ms 715092 KB Output is correct
11 Correct 279 ms 714580 KB Output is correct
12 Correct 55 ms 157088 KB Output is correct
13 Correct 97 ms 289876 KB Output is correct
14 Correct 149 ms 448268 KB Output is correct
15 Correct 255 ms 713196 KB Output is correct
16 Correct 244 ms 713040 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 2 ms 23132 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 2 ms 21084 KB Output is correct
9 Correct 2 ms 21084 KB Output is correct
10 Correct 2 ms 23132 KB Output is correct
11 Correct 2 ms 22996 KB Output is correct
12 Correct 2 ms 20984 KB Output is correct
13 Incorrect 2 ms 21084 KB Output isn't correct
14 Halted 0 ms 0 KB -