제출 #236687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236687		_7_7_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	491 ms	815736 KiB

joi2019_ho_t3

#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
	
int n, cnt[N][3], dp[N][N][N][3], c[3];
vi pos[3];
string s;


inline int get (int l, int r, int i) {
	if (l > r)
		return 0;
	return cnt[r][i] - cnt[l - 1][i];
}


main () {
	cin >> n >> s;
	s = "#" + s;
	
	memset(dp, -1, sizeof(dp));

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j)
			cnt[i][j] = cnt[i - 1][j];
		if (s[i] == 'R') {
			++cnt[i][0]; 
			pos[0].pb(i);
		} else if (s[i] == 'Y') {
			++cnt[i][1]; 
			pos[1].pb(i);
		} else {
			++cnt[i][2]; 
			pos[2].pb(i);
		}
	}

	int cnt0 = cnt[n][0], cnt1 = cnt[n][1], cnt2 = cnt[n][2];
	for (int i = 0; i <= cnt0; ++i)
		for (int j = 0; j <= cnt1; ++j)
			for (int x = 0; x <= cnt2; ++x)
				for (int lst = 0; lst < 3; ++lst)
					dp[i][j][x][lst] = inf;

	for (int lst = 0; lst < 3; ++lst)
		dp[0][0][0][lst] = 0;

	for (c[0] = 0; c[0] <= cnt0; ++c[0])
		for (c[1] = 0; c[1] <= cnt1; ++c[1])
			for (c[2] = 0; c[2] <= cnt2; ++c[2]) 
				for (int lst = 0; lst < 3; ++lst) {
					int cost = 0, c0 = c[0] - !lst, c1 = c[1] - (lst == 1), c2 = c[2] - (lst == 2); 
					if (c1 < 0 || c0 < 0 || c2 < 0)
						continue;

					if (lst && c[0]) 
						cost += get(pos[lst][c[lst] - 1], pos[0][c[0] - 1], 0);
					if (lst != 1 && c[1])
						cost += get(pos[lst][c[lst] - 1], pos[1][c[1] - 1], 1);
					if (lst != 2 && c[2])
						cost += get(pos[lst][c[lst] - 1], pos[2][c[2] - 1], 2);
				
					if (lst)
						dp[c[0]][c[1]][c[2]][lst] = min(dp[c[0]][c[1]][c[2]][lst], dp[c0][c1][c2][0] + cost);
					if (lst != 1)
						dp[c[0]][c[1]][c[2]][lst] = min(dp[c[0]][c[1]][c[2]][lst], dp[c0][c1][c2][1] + cost);
					if (lst != 2)
						dp[c[0]][c[1]][c[2]][lst] = min(dp[c[0]][c[1]][c[2]][lst], dp[c0][c1][c2][2] + cost);
				}

	int ans = min({dp[cnt0][cnt1][cnt2][0], dp[cnt0][cnt1][cnt2][1], dp[cnt0][cnt1][cnt2][2]});
	if (ans == inf)
		ans = -1;
	cout << ans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp:52:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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