oj.uz

답안 #142739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
142739 2019-08-10T15:59:12 Z DrumpfTheGodEmperor Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 434 ms 196276 KB 
#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 405;
int n, dp[N][405][N][3], cntPrefix[N][3];
string s;
vector<int> reds, greens, yellows;
int getRealPosition(int ogPos, int prvRed, int prvGreen, int prvYellow) {
	//prvRed - cntPrefix[ogPos][0] is the number of reds that are moved to before ogPos
	int ans = 0;
	ans += max(0, prvRed - cntPrefix[ogPos][0]);
	ans += max(0, prvGreen - cntPrefix[ogPos][1]);
	ans += max(0, prvYellow - cntPrefix[ogPos][2]);
	return ogPos + ans + 1; //Difference between array indices and dp indices.
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	fw (i, 0, s.length()) {
		if (s[i] == 'R') reds.pb(i);
		else if (s[i] == 'G') greens.pb(i);
		else yellows.pb(i);
	}
	//0: red, 1: green, 2: yellow
	fw (i, 0, s.length()) {
		fw (color, 0, 3) cntPrefix[i][color] = (i ? cntPrefix[i - 1][color] : 0);
		if (s[i] == 'R') cntPrefix[i][0]++;
		else if (s[i] == 'G') cntPrefix[i][1]++;
		else cntPrefix[i][2]++;
	}
	fw (r, 0, n + 1) fw (g, 0, n + 1) fw (color, 0, 3) dp[1][r][g][color] = inf;
	//dp(i, r, g, color): Minimal cost for the first i items, j reds and k greens, i - j - k yellows. The
	//last leave is colored "color".
	if (reds.size() > 0) dp[1][1][0][0] = reds[0];
	if (greens.size() > 0) dp[1][0][1][1] = greens[0];
	if (yellows.size() > 0) dp[1][0][0][2] = yellows[0];
	fw (i, 2, n + 1) fw (r, 0, min((i + 1) / 2, (int)reds.size()) + 1) fw (g, 0, min(i - r, (int)greens.size()) + 1)
																					fw (color, 0, 3) {
//		cout << "dp[" << i << "][" << r << "][" << g << "][" << color << "]\n";
		dp[i][r][g][color] = inf;
		if (color == 0 && r == 0) continue;
		if (color == 1 && g == 0) continue;
		if (color == 2 && i - r - g == 0) continue;
		fw (prvColor, 0, 3) if (prvColor != color) {
			int newr = r, newg = g;
			if (color == 0) newr--;
			if (color == 1) newg--;
			if (newr < 0 || newg < 0) continue;
			if (i - 1 - newr - newg < 0) continue;
			if (newr > i / 2) continue;
//			cout << "prv state = " << i - 1 << " " << newr << " " << newg << " " << prvColor << " dp = " << dp[i - 1][newr][newg][prvColor] << "\n";
			dp[i][r][g][color] = min(dp[i][r][g][color], dp[i - 1][newr][newg][prvColor]);
		}
		if (dp[i][r][g][color] == inf) continue; //Non - valid state
		int y = i - r - g;
		if (y > yellows.size()) continue;
		if (color == 0) {
			dp[i][r][g][color] += getRealPosition(reds[r - 1], r - 1, g, y) - i;
		} else if (color == 1) {
			dp[i][r][g][color] += getRealPosition(greens[g - 1], r, g - 1, y) - i;
		} else {
			dp[i][r][g][color] += getRealPosition(yellows[y - 1], r, g, y - 1) - i;
		}
	}
	int ans = inf;
	fw (color, 0, 3) ans = min(ans, dp[n][reds.size()][greens.size()][color]);
	if (ans == inf) cout << "-1";
	else cout << ans;
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fw(i, l, r) for (int i = l; i < r; i++)
joi2019_ho_t3.cpp:34:6:
  fw (i, 0, s.length()) {
      ~~~~~~~~~~~~~~~~                  
joi2019_ho_t3.cpp:34:2: note: in expansion of macro 'fw'
  fw (i, 0, s.length()) {
  ^~
joi2019_ho_t3.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fw(i, l, r) for (int i = l; i < r; i++)
joi2019_ho_t3.cpp:40:6:
  fw (i, 0, s.length()) {
      ~~~~~~~~~~~~~~~~                  
joi2019_ho_t3.cpp:40:2: note: in expansion of macro 'fw'
  fw (i, 0, s.length()) {
  ^~
joi2019_ho_t3.cpp:71:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (y > yellows.size()) continue;
       ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Incorrect 2 ms 760 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Incorrect 2 ms 760 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 399 ms 196172 KB Output is correct
3 Correct 396 ms 195244 KB Output is correct
4 Correct 396 ms 196116 KB Output is correct
5 Correct 406 ms 196136 KB Output is correct
6 Correct 399 ms 196152 KB Output is correct
7 Correct 401 ms 195192 KB Output is correct
8 Correct 432 ms 195324 KB Output is correct
9 Correct 392 ms 194168 KB Output is correct
10 Correct 403 ms 196124 KB Output is correct
11 Correct 401 ms 196276 KB Output is correct
12 Correct 77 ms 53356 KB Output is correct
13 Correct 153 ms 93304 KB Output is correct
14 Correct 247 ms 134348 KB Output is correct
15 Correct 397 ms 196116 KB Output is correct
16 Correct 434 ms 196264 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Incorrect 2 ms 760 KB Output isn't correct
11 Halted 0 ms 0 KB -