Submission #1281327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281327		flo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	489 ms	1022148 KiB

joi2019_ho_t3

#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];

void flo(int ID) {
	int n; cin >> n;
	
	for (int x = 1; x <= n; x++) {
		char ch; cin >> ch;
		
		int v = 0;
		
		if (ch == 'G') v = 1;
		if (ch == 'Y') v = 2;
		
		for (int c = 0; c < 3; c++) {
			pre[c][x] = pre[c][x-1];
		}
		
		pre[v][x]++, pos[v].push_back(x);
	}
	
	int sz[] = {-1, -1, -1};
	
	for (int c = 0; c < 3; c++) {
		sz[c] = pos[c].size();
	}
	
	dp[0][0][0][3] = 0;
	
	for (int x = 0; x <= sz[0]; x++) {
		for (int y = 0; y <= sz[1]; y++) {
			for (int z = 0; z <= sz[2]; z++) {
				for (int pc = 0; pc < 4; pc++) {
					if (dp[x][y][z][pc] == 2303) continue;
					
					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);
						
						dp[x+1][y][z][0] = min(dp[x+1][y][z][0], dp[x][y][z][pc]+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);
						
						dp[x][y+1][z][1] = min(dp[x][y+1][z][1], dp[x][y][z][pc]+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);
						
						dp[x][y][z+1][2] = min(dp[x][y][z+1][2], dp[x][y][z][pc]+cst);
					}
				}
			}
		}
	}
	
	int ans = 2303;
	
	for (int pc = 0; pc < 3; pc++) {
		ans = min(ans, dp[sz[0]][sz[1]][sz[2]][pc]);
	}
	
	cout << (ans == 2303 ? -1 : 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);
    }
    
    for (int x = 0; x <= N; x++) {
    	for (int y = 0; y <= N; y++) {
    		for (int z = 0; z <= N; z++) {
    			for (int pc = 0; pc < 4; pc++) {
    				dp[x][y][z][pc] = 2303;
				}
			}
		}
	}
    
    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:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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