Submission #1281378

#TimeUsernameProblemLanguageResultExecution timeMemory
1281378floGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
533 ms1041212 KiB
#include <bits/stdc++.h>
#define task "testing"
#define multitest 0
using namespace std;

const int N = 400;

vector<int> pos[3];

int pre[3][N+5], dp[N+5][N+5][N+5][4], n, sz[3];

int calc(int x, int y, int z, int pc) {
	if (x+y+z == n) return 0;
	
	if (dp[x][y][z][pc] != -1) {
		return dp[x][y][z][pc];
	}
	
	int res = 2303;
	
	if (pc != 0 && x < sz[0]) {
		int cur = pos[0][x], cst = 0;
		
		cst += max(0, pre[1][cur]-y);
		cst += max(0, pre[2][cur]-z);
		
		res = min(res, calc(x+1, y, z, 0)+cst);
	}
	if (pc != 1 && y < sz[1]) {
		int cur = pos[1][y], cst = 0;
		
		cst += max(0, pre[0][cur]-x);
		cst += max(0, pre[2][cur]-z);
		
		res = min(res, calc(x, y+1, z, 1)+cst);
	}
	if (pc != 2 && z < sz[2]) {
		int cur = pos[2][z], cst = 0;
		
		cst += max(0, pre[0][cur]-x);
		cst += max(0, pre[1][cur]-y);
		
		res = min(res, calc(x, y, z+1, 2)+cst);
	}
	
	return dp[x][y][z][pc] = res;
}

void flo(int ID) {
	cin >> n;
	
	sz[0] = sz[1] = sz[2] = 0;
	
	for (int x = 1; x <= n; x++) {
		char ch; cin >> ch;
		
		int v = 0;
		
		if (ch == 'G') v = 1;
		if (ch == 'Y') v = 2;
		
		pos[v].push_back(x), sz[v]++;
		
		for (int c = 0; c < 3; c++) {
			pre[c][x] = pre[c][x-1];
		}
		
		pre[v][x]++;
	}
	
	int ans = calc(0, 0, 0, 3);
	
	if (ans == 2303) ans = -1;
	
	cout << ans << "\n";
}

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

    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    memset(dp, -1, sizeof(dp));
    
    int TCS = 1, ID = 1;

    if (multitest) {
        cin >> TCS;
    }

    while (TCS--) flo(ID++);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(task".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...