oj.uz

Submission #136896

# Submission time Handle Problem Language Result Execution time Memory
136896 2019-07-26T13:28:45 Z SirCeness Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 149 ms 163036 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 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]);
		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]);
		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]);
		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;

	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;

	//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:67:10: warning: unused variable 'start' [-Wunused-variable]
  clock_t start = clock();
          ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Incorrect 3 ms 508 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Incorrect 3 ms 508 KB Output isn't correct
12 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 126 ms 163004 KB Output is correct
3 Correct 127 ms 162168 KB Output is correct
4 Correct 126 ms 162904 KB Output is correct
5 Correct 149 ms 162936 KB Output is correct
6 Correct 125 ms 163024 KB Output is correct
7 Correct 125 ms 162068 KB Output is correct
8 Correct 142 ms 162080 KB Output is correct
9 Correct 122 ms 161272 KB Output is correct
10 Correct 125 ms 163036 KB Output is correct
11 Correct 122 ms 162936 KB Output is correct
12 Correct 43 ms 44184 KB Output is correct
13 Correct 60 ms 77176 KB Output is correct
14 Correct 85 ms 111328 KB Output is correct
15 Correct 122 ms 162868 KB Output is correct
16 Correct 121 ms 162940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Incorrect 3 ms 508 KB Output isn't correct
12 Halted 0 ms 0 KB -