Submission #497359

#	Time	Username	Problem	Language	Result	Execution time	Memory
497359		vinnipuh01	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	1 ms	588 KiB

joi2019_ho_t3

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int dp[ 1001 ][ 4 ];
string ss[ 1001 ][ 4 ];
vector <int> r, g, v;
bool b1, b2;

main () {
	int n;
	cin >> n;
	string s, s1, s2;
	cin >> s;
	for ( int i = 0; i < n; i ++ ) {
		if ( s[ i ] == 'R' ) {
			r.push_back( i );
			sum ++;
		}
		else if ( s[ i ] == 'G' ) {
			g.push_back( i );
			ans ++;
		}
		else {
			v.push_back( i );
			num ++;
		}
	}
	mx = max( num, max( sum, ans ) );
	if ( mx > ( n + 1 ) / 2 ) {
		cout << "-1";
		return 0;
	}
	dp[ 0 ][ 1 ] = dp[ 0 ][ 2 ] = dp[ 0 ][ 3 ] = -1;
	for ( int i = 0; i < n; i ++ ) {
		if ( s[ i ] == 'R' && dp[ 0 ][ 1 ] == -1 ) {
			dp[ 0 ][ 1 ] = i;
			ss[ 0 ][ 1 ] = s;
			ss[ 0 ][ 1 ].erase( ss[ 0 ][ 1 ].begin() + i );
		}
		if ( s[ i ] == 'G' && dp[ 0 ][ 2 ] == -1 ) {
			dp[ 0 ][ 2 ] = i;
			ss[ 0 ][ 2 ] = s;
			ss[ 0 ][ 2 ].erase( ss[ 0 ][ 2 ].begin() + i );
		}
		if ( s[ i ] == 'Y' && dp[ 0 ][ 3 ] == -1 ) {
			dp[ 0 ][ 3 ] = i;
			ss[ 0 ][ 3 ] = s;
			ss[ 0 ][ 3 ].erase( ss[ 0 ][ 3 ].begin() + i );
		}
	}
	if ( dp[ 0 ][ 1 ] == -1 )
		dp[ 0 ][ 1 ] = mn;
	if ( dp[ 0 ][ 2 ] == -1 )
		dp[ 0 ][ 2 ] = mn;
	if ( dp[ 0 ][ 3 ] == -1 )
		dp[ 0 ][ 3 ] = mn;
	for ( int i = 1; i < n; i ++ ) {
			sum = dp[ i - 1 ][ 1 ];
			s1 = ss[ i - 1 ][ 1 ];
			b1 = b2 = 0;
			for ( int j = 0; j < ss[ i - 1 ][ 1 ].size(); j ++ ) {
				if ( ss[ i - 1 ][ 1 ][ j ] == 'Y' ) {
					sum += j;
					b1 = 1;
					s1.erase( s1.begin() + j );
					break;
				}
			}
			num = dp[ i - 1 ][ 2 ];
			s2 = ss[ i - 1 ][ 2 ];
			for ( int j = 0; j < ss[ i - 1 ][ 2 ].size(); j ++ ) {
				if ( s2[ j ] == 'Y' ) {
					num += j;
					b2 = 1;
					s2.erase( s2.begin() + j );
					break;
				}
			}
		if ( !b1 && b2 ) {
			dp[ i ][ 3 ] = num;
			ss[ i ][ 3 ] = s2;
		}
		else if ( !b2 && b1 ) {
			dp[ i ][ 3 ] = sum;
			ss[  i][ 3 ] = s1;
		}
		else if ( !b1 && !b2 )
			dp[ i ][ 3 ] = mn;
		else if ( num < sum ) {
			dp[ i ][ 3 ] = num;
			ss[ i ][ 3 ] = s2;
		}
		else {
			dp[ i ][ 3 ] = sum;
			ss[  i][ 3 ] = s1;
		}
		
			sum = dp[ i - 1 ][ 2 ];
			s1 = ss[ i - 1 ][ 2 ];
			b1 = b2 = 0;
			for ( int j = 0; j < ss[ i - 1 ][ 2 ].size(); j ++ ) {
				if ( s1[ j ] == 'R' ) {
					sum += j;
					b1 = 1;
					s1.erase( s1.begin() + j );
					break;
				}
			}
			num = dp[ i - 1 ][ 3 ];
			s2 = ss[ i - 1 ][ 3 ];
			for ( int j = 0; j < ss[ i - 1 ][ 3 ].size(); j ++ ) {
				if ( s2[ j ] == 'R' ) {
					num += j;
					b2 = 1;
					s2.erase( s2.begin() + j );
					break;
				}
			}
		if ( !b1 && b2 ) {
			dp[ i ][ 1 ] = num;
			ss[ i ][ 1 ] = s2;
		}
		else if ( !b2 && b1 ) {
			dp[ i ][ 1 ] = sum;
			ss[  i][ 1 ] = s1;
		}
		else if ( !b1 && !b2 )
			dp[ i ][ 1 ] = mn;
		else if ( num < sum ) {
			dp[ i ][ 1 ] = num;
			ss[ i ][ 1 ] = s2;
		}
		else {
			dp[ i ][ 1 ] = sum;
			ss[  i][ 1 ] = s1;
		}
			sum = dp[ i - 1 ][ 1 ];
			s1 = ss[ i - 1 ][ 1 ];
			b1 = b2 = 0;
			for ( int j = 0; j < ss[ i - 1 ][ 1 ].size(); j ++ ) {
				if ( s1[ j ] == 'G' ) {
					sum += j;
					b1 = 1;
					s1.erase( s1.begin() + j );
					break;
				}
			}
			num = dp[ i - 1 ][ 3 ];
			s2 = ss[ i - 1 ][ 3 ];
			for ( int j = 0; j < ss[ i - 1 ][ 3 ].size(); j ++ ) {
				if ( s2[ j ] == 'G' ) {
					num += j;
					b2 = 1;
					s2.erase( s2.begin() + j );
					break;
				}
			}
		if ( !b1 && b2 ) {
			dp[ i ][ 2 ] = num;
			ss[ i ][ 2 ] = s2;
		}
		else if ( !b2 && b1 ) {
			dp[ i ][ 2 ] = sum;
			ss[  i][ 2 ] = s1;
		}
		else if ( !b1 && !b2 )
			dp[ i ][ 2 ] = mn;
		else if ( num < sum ) {
			dp[ i ][ 2 ] = num;
			ss[ i ][ 2 ] = s2;
		}
		else {
			dp[ i ][ 2 ] = sum;
			ss[  i][ 2 ] = s1;
		}
//		cout << i << " - " << dp[ i ][ 1 ] << " " << dp[ i ][ 2 ] << " " << dp[  i][ 3 ] << "\n";
	}
	cout << min( dp[ n - 1 ][ 1 ], min( dp[ n - 1 ][ 2 ], dp[ n - 1 ][ 3 ] ) );
}



/*
20
YYGYYYGGGGRGYYGRGRYG
1 - YGYYYYGGGGRGYYGRGRYG
2- YGYYYGYGGGRGYYGRGRYG
3 - YGYYGYYGGGRGYYGRGRYG
4 - YGYGYYYGGGRGYYGRGRYG
YGYGYGYGYGRGYGYRGRYG

*/

Compilation message (stderr)

joi2019_ho_t3.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main () {
      | ^~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for ( int j = 0; j < ss[ i - 1 ][ 1 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:113:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for ( int j = 0; j < ss[ i - 1 ][ 2 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:143:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    for ( int j = 0; j < ss[ i - 1 ][ 2 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:153:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |    for ( int j = 0; j < ss[ i - 1 ][ 3 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:182:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |    for ( int j = 0; j < ss[ i - 1 ][ 1 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:192:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |    for ( int j = 0; j < ss[ i - 1 ][ 3 ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25