Submission #497986

#	Time	Username	Problem	Language	Result	Execution time	Memory
497986		mansur	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	2 ms	1280 KiB

joi2019_ho_t3

#include<bits/stdc++.h>	
/* 
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
*/ 
//01001101 01100001 01101011 01101000 01100001  01100111 01100001 01111001 
 
using namespace std;
 
#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()                                                                   
#define ld double
#define ull unsigned long long
#define ff first                                         
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>                          
#define E exit (0)
#define int long long
 
const int inf = 1e15, N = 1500, mod = 998244353;                    
 
vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int cnt[N][3];
	
vector<int> pos[3];

main() {                                                         
	//freopen("triangles.in", "r", stdin);                                                                                     
	//freopen("triangles.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(NULL);                                                                                        
	cin.tie(NULL);
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 1; i <= n; i++) {
		cnt[i][0] = cnt[i - 1][0];
		cnt[i][1] = cnt[i - 1][1];
		cnt[i][2] = cnt[i - 1][2];
	 	if (s[i - 1] == 'R') {
	 		cnt[i][0]++;
	 		pos[0].pb(i);
	 	}
	 	if (s[i - 1] == 'G') {
	 		cnt[i][1]++;
	 		pos[1].pb(i);
	 	}
	 	if (s[i - 1] == 'Y') {
	 		cnt[i][2]++;
	 		pos[2].pb(i);
	 	}
	}
	if (cnt[n][0] > cnt[n][1] + cnt[n][2] + 1) cout << -1, E;
	if (cnt[n][1] > cnt[n][0] + cnt[n][2] + 1) cout << -1, E;
	if (cnt[n][2] > cnt[n][1] + cnt[n][2] + 1) cout << -1, E;
	int dp[cnt[n][0] + 1][cnt[n][1] + 1][cnt[n][2] + 1][3];
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int i = 0; i <= cnt[n][0]; i++) {
		for (int j = 0; j <= cnt[n][1]; j++) {
			for (int k = 0; k <= cnt[n][2]; k++) {
				if (!i && !j && !k) continue;
				int len = i + j + k;
				if (!i) dp[i][j][k][0] = inf;
				else {
				 	int p = pos[0][i - 1];
				 	p += max(0ll, j - cnt[p][1]) + max(0ll, k - cnt[p][2]);
				 	dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + p - len;
				}
				if (!j) dp[i][j][k][1] = inf;
				else {
				 	int p = pos[1][j - 1];
				 	p += max(0ll, i - cnt[p][0]) + max(0ll, k - cnt[p][2]);
				 	dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + p - len;
				}
				if (!k) dp[i][j][k][2] = inf;
				else {
				 	int p = pos[2][k - 1];
				 	p += max(0ll, j - cnt[p][1]) + max(0ll, i - cnt[p][0]);
				 	dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + p - len;
				}
			}                     
		}
	}
	cout << min(dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][0], min(dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][1], dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][2]));
}

Compilation message (stderr)

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

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