oj.uz

Submission #136901

# Submission time Handle Problem Language Result Execution time Memory
136901 2019-07-26T13:45:03 Z SirCeness Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 125 ms 162960 KB 
#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define ppair(x) "(" << x.first << ", " << x.second << ")"
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

string s;

int dist(string str){
	string ana = s;
	ll ans = 0;
	int say = 0;
	for (int i = str.size()-1; i >= 0; i--){
		for (int j = ana.size()-1; j >= 0; j--){
			if (ana[j] == str[i]){
				ana[j] = 'x';
				say++;
				break;
			} else if (ana[j] != 'x') ans++;
		}
	}
	if (say != str.size()) return 1000000000;
	return ans;
}

int dp[404][404][404][4];	
vector<int> rler, gler, yler;
int sufsumg[404];
int sufsumy[404];
int sufsumr[404];

int f(int r, int g, int y, int last){
	//cout << "f(" << r << ", "  << g << ", " << y << ", " << last << ")" << endl;
	if (dp[r][g][y][last] != -1) return dp[r][g][y][last];
	int minn = 400*400+2;
	if ((r > 0) && (last != 0)){
		int ret = f(r-1, g, y, 0);
		ret += max(0, (int)s.size() - (r+g+y) - rler[rler.size()-r] + max(0, g-sufsumg[(int)s.size() - (r+g+y)+1]) + max(0, y-sufsumy[(int)s.size() - (r+g+y)+1]));
		minn = min(minn, ret);
	} 
	if (g > 0 && last != 1){
		int ret = f(r, g-1, y, 1);
		ret += max(0, (int)s.size() - (r+g+y) - gler[gler.size()-g] + max(0, r-sufsumr[(int)s.size() - (r+g+y)+1]) + max(0, y-sufsumy[(int)s.size() - (r+g+y)+1]));
		minn = min(minn, ret);
	} 
	if (y > 0 && last != 2){
		int ret = f(r, g, y-1, 2);
		ret += max(0, (int)s.size() - (r+g+y) - yler[yler.size()-y] + max(0, r-sufsumr[(int)s.size() - (r+g+y)+1]) + max(0, g-sufsumg[(int)s.size() - (r+g+y)+1]));
		minn = min(minn, ret);
	}
	if (g == 0 && r == 0 && y == 0){
		return dp[r][g][y][last] = 0;
	} 
	return dp[r][g][y][last] = minn;
}

int main(){
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
	
	clock_t start = clock();

	int n;
	cin >> n;
	cin >> s;
	n = s.size();

	int r = 0, g = 0, y = 0;
	for (int i = 0; i < n; i++){
		r += s[i] == 'R';
		g += s[i] == 'G';
		y += s[i] == 'Y';
		if (s[i] == 'R') rler.pb(i);
		else if (s[i] == 'G') gler.pb(i);
		else yler.pb(i);
	}

	for (int i1 = 0; i1 <= r; i1++)
		for (int i2 = 0; i2 <= g; i2++)
			for (int i3 = 0; i3 <= y; i3++)
				for (int i4 = 0; i4 < 4; i4++)
					dp[i1][i2][i3][i4] = -1;

	int sufr = 0, sufg = 0, sufy = 0;
	for (int i = n-1; i >= 0; i--){
		if (s[i] == 'R') sufr++;
		if (s[i] == 'G') sufg++;
		if (s[i] == 'Y') sufy++;
		sufsumr[i] = sufr;
		sufsumg[i] = sufg;
		sufsumy[i] = sufy;	  
	}

	//cout << f(1, 0, 0, 1) << endl;
	int ans = f(r, g, y, 3);
	//int ans = 0;
	if (ans >= 400*400+2) cout << -1 << endl;
	else cout << ans << endl;
	//cout << "bitti" << endl;

	//cout << 1000.0*(clock()-start)/(double)CLOCKS_PER_SEC << "ms" << endl;

}

Compilation message

joi2019_ho_t3.cpp: In function 'int dist(std::__cxx11::string)':
joi2019_ho_t3.cpp:31:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (say != str.size()) return 1000000000;
      ~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:70:10: warning: unused variable 'start' [-Wunused-variable]
  clock_t start = clock();
          ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 124 ms 162936 KB Output is correct
3 Correct 123 ms 162144 KB Output is correct
4 Correct 123 ms 162960 KB Output is correct
5 Correct 123 ms 162908 KB Output is correct
6 Correct 124 ms 162908 KB Output is correct
7 Correct 121 ms 162168 KB Output is correct
8 Correct 122 ms 162172 KB Output is correct
9 Correct 121 ms 161376 KB Output is correct
10 Correct 121 ms 162908 KB Output is correct
11 Correct 123 ms 162932 KB Output is correct
12 Correct 41 ms 44156 KB Output is correct
13 Correct 60 ms 77308 KB Output is correct
14 Correct 83 ms 111352 KB Output is correct
15 Correct 122 ms 162952 KB Output is correct
16 Correct 125 ms 162940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -