Submission #209217

#	Time	Username	Problem	Language	Result	Execution time	Memory
209217		kostia244	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	509 ms	786296 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;
}
int pp[maxn][maxn][3][3];
void lb(int c, int n1, int i, int j, int &ans) {
	if(pp[i][j][c][n1]!= -1) {
		ans -= pp[i][j][c][n1];
		return;
	}
	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 -= (pp[i][j][c][n1]=min(t+1, j));
	else
		pp[i][j][c][n1] = 0;
}
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;
	lb(c, n1, i, j, ans);
	lb(c, n2, i, k, ans);
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(pp, -1, sizeof pp);
	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 <= p[0].size(); i++) {
		for(int j = 0; j <= p[1].size(); j++) {
			for(int k = 0; k <= p[2].size(); 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 'void lb(int, int, int, int, int&)':
joi2019_ho_t3.cpp:32: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: In function 'int cost(int, int, int, int, int)':
joi2019_ho_t3.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(p[c].size()<=i) return 1<<20;
     ~~~~~~~~~~~^~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i <= p[0].size(); i++) {
                 ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= p[1].size(); j++) {
                  ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k <= p[2].size(); k++) {
                   ~~^~~~~~~~~~~~~~

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