Submission #72311

#	Time	Username	Problem	Language	Result	Execution time	Memory
72311		RR rangers (#118)	Dstorv (FXCUP3_dstorv)	C++17	0 / 100	8 ms	1380 KiB

dstorv

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>
#define MOD ((i64)(1e9+7))

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

// table[r][h] = R이 r개, H가 h개 있을 때 둘다 0개가 될 확률
i64 table[5001][5001];

i64 ipow(i64 x, i64 k)
{
	if (k == 0)
		return 1;

	i64 half = ipow(x, k / 2);

	half = (half * half) % MOD;

	if (k % 2 == 0)
		return half;
	else
		return (half * x) % MOD;
}

int main()
{
	int n, r, h;
	scanf("%d %d %d", &n, &r, &h);

	string s;

	cin >> s;

	table[0][0] = 1;

	i64 flowerp, handp;
	i64 denom = ipow(r + h, MOD - 2);

	flowerp = (h * denom) % MOD;
	handp = (r * denom) % MOD;

	for(int flower = 0; flower <= n; flower ++)
	{
		for(int hand = 0; hand <= n; hand++)
		{
			if (flower == 0 && hand == 0)
				continue;

			table[flower][hand] = 1;
			
			if (flower > 0)
				table[flower][hand] = handp * table[flower - 1][hand];

			if (hand > 0)
				table[flower][hand] = flowerp * table[flower][hand - 1];
		}
	}

	int a, b;
	scanf("%d %d", &a, &b);

	i64 ans = 0;
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] != 'H' || s[i + 1] != 'R')
			continue;

		int leftmost = -1;
		for (int j = 0; j <= i; j++)
		{
			if (s[j] == 'R')
			{
				leftmost = j;
				break;
			}
		}

		i64 leftp = 1;
		int hl = 0, hr = 0;
		int remainr = 0;

		for (int j = 0; j <= i; j++)
		{
			if (s[j] != 'H')
			{
				remainr++;
				continue;
			}

			if (j <= leftmost)
				hl++;
			else
				hr++;
		}

		if (leftmost == -1)
		{
			if (hl != b)
				continue;
		}
		else
		{
			int remain = b - hl;

			if (remain < 0)
				continue;

			int need = hr - remain;

			leftp = table[remainr][need];
		}

		i64 rightp = 1;

		int rightmost = -1;
		for (int j = n - 1; j > i; j--)
		{
			if (s[j] == 'H')
			{
				rightmost = j;
				break;
			}
		}

		int rl = 0, rr = 0;
		int remainh = 0;

		for (int j = n - 1; j > i ; j--)
		{
			if (s[j] != 'R')
			{
				remainh++;
				continue;
			}

			if (j >= rightmost)
				rr++;
			else
				rl++;
		}

		if (rightmost == -1)
		{
			if (rr != a)
				continue;
		}
		else
		{
			int remain = a - rr;

			if (remain < 0)
				continue;

			int need = rl - remain;

			rightp = table[need][remainh];
		}

		i64 p = (leftp * rightp) % MOD;

		ans = (ans + p) % MOD;
	}

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

dstorv.cpp: In function 'int main()':
dstorv.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~
dstorv.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 29
• Subtask 3: 0 / 62