Submission #1221444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221444		mingga	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	135 ms	134852 KiB

joi2019_ho_t3

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
int n;
string s;

vector<int> pos[3];
int ps[405][3];
int id[130];

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> s;
	s = ' ' + s;
	id['R'] = 0, id['G'] = 1, id['Y'] = 2;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) ps[i][j] = ps[i - 1][j];
		ps[i][id[s[i]]]++;
		pos[id[s[i]]].pb(i);
	}
	int c0 = ps[n][0], c1 = ps[n][1], c2 = ps[n][2];
	vector<vector<vector<vector<int>>>> dp(c0 + 1, vector<vector<vector<int>>>(c1 + 1, vector<vector<int>>(c2 + 1, vector<int>(3, inf))));
    for(int i = 0; i < 3; i++) {
    	dp[0][0][0][i] = 0;
    }
    for(int i = 0; i <= c0; i++) {
    	for(int j = 0; j <= c1; j++) {
    		for(int k = 0; k <= c2; k++) {
    			if(i > 0) {
    				int p = pos[0][i - 1];
    				int ext = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]);
    				ext +=  max(0, ps[p][1] - j) + max(0, ps[p][2] - k);
    				dp[i][j][k][0] = min(dp[i][j][k][0], ext);
    			}
    			if(j > 0) {
    				int p = pos[1][j - 1];
    				int ext = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]);
    				ext +=  max(0, ps[p][0] - i) + max(0, ps[p][2] - k);
    				dp[i][j][k][1] = min(dp[i][j][k][1], ext);
    			}
    			if(k > 0) {
    				int p = pos[2][k - 1];
    				int ext = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]);
    				ext +=  max(0, ps[p][1] - j) + max(0, ps[p][0] - i);
    				dp[i][j][k][2] = min(dp[i][j][k][2], ext);
    			}
    		}
    	}
    }
    int ans = inf;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[c0][c1][c2][i]);
    cout << (ans == inf ? -1 : ans) << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:25:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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