oj.uz

답안 #136900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136900 2019-07-26T13:41:52 Z SirCeness Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 151 ms 163064 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)]) + max(0, y-sufsumy[(int)s.size() - (r+g+y)]));
		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)]) + max(0, y-sufsumy[(int)s.size() - (r+g+y)]));
		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)]) + max(0, g-sufsumg[(int)s.size() - (r+g+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;
	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

# 결과 실행 시간 메모리 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 121 ms 163064 KB Output is correct
3 Correct 120 ms 162168 KB Output is correct
4 Correct 121 ms 162920 KB Output is correct
5 Correct 122 ms 162888 KB Output is correct
6 Correct 121 ms 162936 KB Output is correct
7 Correct 122 ms 162244 KB Output is correct
8 Correct 120 ms 162168 KB Output is correct
9 Correct 120 ms 161272 KB Output is correct
10 Correct 123 ms 162936 KB Output is correct
11 Correct 123 ms 162940 KB Output is correct
12 Correct 34 ms 44152 KB Output is correct
13 Correct 58 ms 77176 KB Output is correct
14 Correct 89 ms 111436 KB Output is correct
15 Correct 121 ms 162944 KB Output is correct
16 Correct 151 ms 162936 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -