Submission #1303954

#TimeUsernameProblemLanguageResultExecution timeMemory
1303954hoa208Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
11 ms20548 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------
ll n;
string T = "RGY";
string s;
const ll N = 402;
ll f[N][N][4][4];
ll dp(ll i, ll j, ll type, ll type2) {
	assert(j != 0);
	if(i == n) return j == 1 ? 0 : INF;
	if(f[i][j][type][type2] != -1) return f[i][j][type][type2];
	ll type_new = T.find(s[i]);
	if(type_new == type) {
		return f[i][j][type][type2] = dp(i + 1, j + 1, type, type2);
	}
	ll res = INF;
	if(type != 3 && type2 != type_new) {
		res = min(res, dp(i + 1, j, type, type_new) + j);
	}
	if(j == 1) {
		res = min(res, dp(i + 1, j, type_new, type));
	}
	else if(j >= 2)
		res = min(res, dp(i + 1, j - 1, type, type2) + j - 1);
	return f[i][j][type][type2] = res;
	
}
void hbmt() {
	cin >> n;
	cin >> s;
	memset(f, -1, sizeof f);
	ll val = dp(0, 1, 3, 3);
	if(val == INF) cout << -1;
	else cout << val;
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}
	
	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:54:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                 freopen(NAME".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 freopen(NAME".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...