Submission #209212

#	Time	Username	Problem	Language	Result	Execution time	Memory
209212		kostia244	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	712 ms	780572 KiB

joi2019_ho_t3

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,fma,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 405;
void minq(int &a, int b) {
	if(a > b) a = b;
}
int dp[maxn][maxn][maxn][3];
int n;
string s;
vi p[3];
int id(char c) {
	if(c=='R') return 0;
	if(c=='G') return 1;
	return 2;
}
inline int cost(int i, int j, int k, int l, int w) {
	if(l == w) return 1<<20;
	int c, n1, n2;
	if(w==0) {
		c = 0;
		n1 = 1;
		n2 = 2;
	}
	if(w==1) {// i, j, k => j i k
		swap(i, j);
		c = 1;
		n1 = 0;
		n2 = 2;
	}
	if(w==2) {// i, j, k => k, j, i
		swap(i, k);
		c = 2;
		n1 = 1;
		n2 = 0;
	}
	if(p[c].size()<=i) return 1<<20;
	int ans = p[c][i] - i;
	int t, z;
	for(t = 0, z = 1<<9; z>>=1;)
		if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
	if(p[n1].size()&&p[n1][0]<p[c][i])
		ans -= min(t+1, j);
	for(t = 0, z = 1<<9; z>>=1;)
		if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
	if(p[n2].size()&&p[n2][0]<p[c][i])
		ans -= min(t+1, k);
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++) p[id(s[i])].pb(i);
	memset(dp, 0x3f, sizeof dp);
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	int ans = 1<<30;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++) {
				for(int l = 0; l < 3; l++) {
					if(i+j+k==n) ans = min(ans, dp[i][j][k][l]);
					if(dp[i][j][k][l]>n*n) continue;
					minq(dp[i+1][j][k][0], dp[i][j][k][l] + cost(i, j, k, l, 0));
					minq(dp[i][j+1][k][1], dp[i][j][k][l] + cost(i, j, k, l, 1));
					minq(dp[i][j][k+1][2], dp[i][j][k][l] + cost(i, j, k, l, 2));
				}
			}
		}
	}
	if(ans>n*n) ans = -1;
	cout << ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int cost(int, int, int, int, int)':
joi2019_ho_t3.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(p[c].size()<=i) return 1<<20;
     ~~~~~~~~~~~^~~
joi2019_ho_t3.cpp:48:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
      ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
      ~~~^~~~~~~~~~~~~

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