제출 #236682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236682		_7_7_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	509 ms	815740 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) {
					if (!c[lst])
						continue;
					int cost = 0;
					for (int lst1 = 0; lst1 < 3; ++lst1)
						if (lst1 != lst && c[lst1])
							cost += get(pos[lst][c[lst] - 1], pos[lst1][c[lst1] - 1], lst1);

//					cerr << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << cost << endl;
					for (int lst1 = 0; lst1 < 3; ++lst1)
						if (lst != lst1)
							dp[c[0]][c[1]][c[2]][lst] = min(dp[c[0]][c[1]][c[2]][lst], dp[c[0] - (!lst)][c[1] - (lst == 1)][c[2] - (lst == 2)][lst1] + 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: 0 / 25