oj.uz

답안 #1089408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089408 2024-09-16T12:29:29 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 283 ms 705028 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 = 300 + 123;
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, 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( 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, Y - py[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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Incorrect 0 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Incorrect 0 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 243 ms 704960 KB Output is correct
3 Correct 263 ms 701268 KB Output is correct
4 Correct 283 ms 704852 KB Output is correct
5 Correct 229 ms 704852 KB Output is correct
6 Correct 243 ms 704932 KB Output is correct
7 Correct 233 ms 699732 KB Output is correct
8 Correct 233 ms 699732 KB Output is correct
9 Correct 246 ms 696032 KB Output is correct
10 Correct 265 ms 705028 KB Output is correct
11 Correct 238 ms 704852 KB Output is correct
12 Correct 48 ms 139992 KB Output is correct
13 Correct 99 ms 276564 KB Output is correct
14 Correct 156 ms 435792 KB Output is correct
15 Correct 254 ms 703404 KB Output is correct
16 Correct 238 ms 703316 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Incorrect 0 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -