oj.uz

Submission #136904

# Submission time Handle Problem Language Result Execution time Memory
136904 2019-07-26T13:52:43 Z SirCeness Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 138 ms 162976 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);
		int ind = s.size() -r-g-y;
		ret += max(sufsumr[ind]-1, r-1) + max(sufsumg[ind], g) + max(sufsumy[ind], y) - (g+y+r-1);
		minn = min(minn, ret);
	} 
	if (g > 0 && last != 1){
		int ret = f(r, g-1, y, 1);
		int ind = s.size() -r-g-y;
		ret += max(sufsumr[ind], r) + max(sufsumg[ind]-1, g-1) + max(sufsumy[ind], y) - (g+y+r-1);
		minn = min(minn, ret);
	} 
	if (y > 0 && last != 2){
		int ret = f(r, g, y-1, 2);
		int ind = s.size() -r-g-y;
		ret += max(sufsumr[ind], r) + max(sufsumg[ind], g) + max(sufsumy[ind]-1, y-1) - (g+y+r-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:73: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 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Incorrect 2 ms 504 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 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Incorrect 2 ms 504 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 123 ms 162960 KB Output is correct
3 Correct 122 ms 162124 KB Output is correct
4 Correct 138 ms 162932 KB Output is correct
5 Correct 121 ms 162936 KB Output is correct
6 Correct 125 ms 162908 KB Output is correct
7 Correct 122 ms 162148 KB Output is correct
8 Correct 121 ms 162128 KB Output is correct
9 Correct 120 ms 161272 KB Output is correct
10 Correct 122 ms 162896 KB Output is correct
11 Correct 122 ms 162900 KB Output is correct
12 Correct 35 ms 44152 KB Output is correct
13 Correct 59 ms 77224 KB Output is correct
14 Correct 84 ms 111480 KB Output is correct
15 Correct 121 ms 162976 KB Output is correct
16 Correct 122 ms 162936 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 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Incorrect 2 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -