Submission #497908

#	Time	Username	Problem	Language	Result	Execution time	Memory
497908		vinnipuh01	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	131 ms	164836 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[ 401 ][ 401 ][ 401 ][ 3 ];
vector <pair<int, pair<int, int> > > v, vv, v1;

int f( int a, int b ) {
	return min( a, b );
}

main () {
	int n;
	cin >> n;
	string s;
	cin >> s;
	for ( int i = 0; i < s.size(); i ++ ) {
		if ( s[ i ] == 'R' ) {
			sum ++;
			v.push_back( { i, make_pair( vv.size(), v1.size() ) } );
		}
		if ( s[ i ] == 'Y' ) {
			num ++;
			v1.push_back( { i, make_pair( v.size(), vv.size() ) } );
		}
		if ( s[ i ] == 'G' ) {
			mx ++;
			vv.push_back( { i, make_pair( v.size(), v1.size() ) } );
		}
	}
	if ( max( mx, max( num, sum ) )  > ( n + 1 ) / 2 ) {
		cout << "-1";
		return 0;
	}
	for ( int i = 0; i <= sum; i ++ ) {
		for ( int j = 0; j <= mx; j ++ ) {
			for ( int k = 0; k <= num; k ++ ) {
				if ( i + j + k == 0 )
					continue;
				dp[ i ][ j ][ k ][ 1 ] = dp[ i ][ j ][ k ][ 2 ] = dp[ i ][ j ][ k ][ 3 ] = oo;
			}
		}
	}
	for ( int a = 0; a <= sum; a ++ ) {
		for ( int b = 0; b <= mx; b ++ ) {
			for ( int c = 0; c <= num; c ++ ) {
				if ( a ) {
					dp[ a ][ b ][ c ][ 1 ] = min( dp[ a - 1 ][ b ][ c ][ 2 ], dp[ a - 1 ][ b ][ c ][ 3 ] );
					mn = v[ a - 1 ].first;
					mn -= a - 1;
					mn -= f( v[ a - 1 ].second.first, b );
					mn -= f( v[ a - 1 ].second.second, c );
					dp[ a ][ b ][ c ][ 1 ] += mn;
				}
				if ( b ) {
					dp[ a ][ b ][ c ][ 2 ] = min( dp[ a ][ b - 1 ][ c ][ 1 ], dp[ a ][ b - 1 ][ c ][ 3 ] );
					mn = vv[ b - 1 ].first;
					mn -= b - 1;
					mn -= f( vv[ b - 1 ].second.first, a );
					mn -= f( vv[ b - 1 ].second.second, c );
					dp[ a ][ b ][ c ][ 2 ] += mn;
				}
				if ( c ) {
					dp[ a ][ b ][ c ][ 3 ] = min( dp[ a ][ b ][ c - 1 ][ 1 ], dp[ a ][ b ][ c - 1 ][ 2 ] );
					mn = v1[ c - 1 ].first;
					mn -= c - 1;
					mn -= f( v1[ c - 1 ].second.first, a );
					mn -= f( v1[ c - 1 ].second.second, b );
					dp[ a ][ b ][ c ][ 3 ] += mn;
				}
//				cout << a << " " << b << " " << c << " - " << dp[ a ][ b ][ c ][ 1 ] << " " << dp[ a ][ b ][ c ][ 2 ] << " " << dp[ a ][ b ][ c ][ 3 ] << "\n";
			}
		}
	}
	cout << min( dp[ sum ][ mx ][ num ][ 1 ], min( dp[ sum ][ mx ][ num ][ 2 ], dp[ sum ][ mx ][ num ][ 3 ] ) );
}

Compilation message (stderr)

joi2019_ho_t3.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main () {
      | ^~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:58:21: 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]
   58 |  for ( int i = 0; i < s.size(); i ++ ) {
      |                   ~~^~~~~~~~~~
joi2019_ho_t3.cpp:81:76: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
   81 |     dp[ i ][ j ][ k ][ 1 ] = dp[ i ][ j ][ k ][ 2 ] = dp[ i ][ j ][ k ][ 3 ] = oo;
      |                                                       ~~~~~~~~~~~~~~~~~~~~~^
joi2019_ho_t3.cpp:89:89: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
   89 |      dp[ a ][ b ][ c ][ 1 ] = min( dp[ a - 1 ][ b ][ c ][ 2 ], dp[ a - 1 ][ b ][ c ][ 3 ] );
      |                                                                ~~~~~~~~~~~~~~~~~~~~~~~~~^
joi2019_ho_t3.cpp:97:89: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
   97 |      dp[ a ][ b ][ c ][ 2 ] = min( dp[ a ][ b - 1 ][ c ][ 1 ], dp[ a ][ b - 1 ][ c ][ 3 ] );
      |                                                                ~~~~~~~~~~~~~~~~~~~~~~~~~^
joi2019_ho_t3.cpp:105:27: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
  105 |      dp[ a ][ b ][ c ][ 3 ] = min( dp[ a ][ b ][ c - 1 ][ 1 ], dp[ a ][ b ][ c - 1 ][ 2 ] );
      |      ~~~~~~~~~~~~~~~~~~~~~^
joi2019_ho_t3.cpp:110:29: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
  110 |      dp[ a ][ b ][ c ][ 3 ] += mn;
      |      ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
joi2019_ho_t3.cpp:116:104: warning: array subscript 3 is above array bounds of 'long long int [3]' [-Warray-bounds]
  116 |  cout << min( dp[ sum ][ mx ][ num ][ 1 ], min( dp[ sum ][ mx ][ num ][ 2 ], dp[ sum ][ mx ][ num ][ 3 ] ) );
      |                                                                              ~~~~~~~~~~~~~~~~~~~~~~~~~~^

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