Submission #1243675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243675		Bui_Quoc_Cuong	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	75 / 100	753 ms	780440 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ALL(A) A.begin(), A.end()
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define taskname "kieuoanh"
const int N = 5e5 + 5;

int n;
string s;
int dp[405][405][405][3];
vector <int> preR, preG, preY;

int calc(int l, int r, vector <int> v){
	int cnt = 0;
	for(int i = l; i < (int)v.size() && v[i] <= r; i++) cnt++;
	return cnt;
}

void Solve(){
	cin >> n >> s; s = "*" + s;
	FOR(i, 1, n){
		if(s[i] == 'R') preR.push_back(i);
		if(s[i] == 'G') preG.push_back(i);
		if(s[i] == 'Y') preY.push_back(i);
	}
	memset(dp, 0x3f, sizeof dp);
	int n = preR.size(), m = preG.size(), p = preY.size();
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	FOR(i, 0, n){
		FOR(j, 0, m) FOR(k, 0, p){
			FOR(l, 0, 2){
				int &cur = dp[i][j][k][l];
				if(cur >= 1e9) continue;
				if(l != 0 && i + 1 <= n){
					dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], cur + calc(j, preR[i], preG) + calc(k, preR[i], preY));
				}
				if(l != 1 && j + 1 <= m){
					dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], cur + calc(i, preG[j], preR) + calc(k, preG[j], preY));
				}
				if(l != 2 && k + 1 <= p){
					dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], cur + calc(i, preY[k], preR) + calc(j, preY[k], preG));
				}
			}
		}
	}	
	int ans = 2e9;
	FOR(l, 0, 2){
		ans = min(ans, dp[n][m][p][l]);
	}
	cout << (ans >= 1e9 ? - 1 : ans);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
    Solve();
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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