oj.uz

Submission #611725

# Submission time Handle Problem Language Result Execution time Memory
611725 2022-07-29T06:56:43 Z 장태환(#8498) Ljetopica (COI19_ljetopica) C++17
22 / 100
 32 ms 23092 KB 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define int long long
int gt(string& a, string& b)
{
	int i;
	for (i = 0; i < a.size(); i++)
	{
		if (a[i] < b[i])
			return 1;
		else if(a[i] > b[i])
			return -1;
	}
	return 0;
}
int dp[1010][1010][2];
int cnt[1010][1010][2];
int pw[1010];
string s,a,b;
int N, K;
string cs, ce;
pair<int,int> dfs(int n,int k,int p)
{
	if (gt(b, cs)==1 || gt(ce, a)==1||k<0)
	{
		return { 0,0 };
	}
	if (gt(ce, b) != -1 && gt(cs, a) != 1)
	{
		return { dp[n][k][p],cnt[n][k][p] };
	}
	cs[n + 1] = '0';
	ce[n + 1] = '0';
	pair<int, int>lv = dfs(n + 1, k - (p != (s[n + 1] != '0')), s[n + 1] != '0');
	cs[n + 1] = '1';
	ce[n + 1] = '1';
	pair<int, int>rv = dfs(n + 1, k - (p != (s[n + 1] != '1')), s[n + 1] != '1');
	cs[n + 1] = '0';
	return { (((cs[n]=='1')*(lv.second+rv.second)*pw[s.size()-1-n])+lv.first+rv.first)%MOD,(lv.second + rv.second)%MOD };
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin >> N >> K;
	cin >> s>>a>>b;
	a.erase(a.begin());
	b.erase(b.begin());
	int i;
	pw[0] = 1;
	for (i = 1; i <= N; i++)
	{
		pw[i] = pw[i - 1] * 2 % MOD;
	}
	for (i = 0; i < s.size(); i++)
	{
		if (s[i] == 'L')
			s[i] = '0';
		else
			s[i] = '1';
		cs.push_back('0');
		ce.push_back('1');
	}
	for (i = s.size()-1; i >=0; i--)
	{
		if (i == s.size() - 1)
		{
			dp[i][0][0] = s[i] == '1';
			dp[i][0][1] = s[i] == '0';
			cnt[i][0][0] = 1;
			cnt[i][0][1] = 1;
		}
		else
		{
			int j;
			for (j = 0; j <= s.size()-1-i; j++)
			{
				dp[i][j][0] += dp[i + 1][j][0] + (s[i] == '1') * cnt[i + 1][j][0] * pw[s.size() - 1 - i];
				dp[i][j][1] += dp[i + 1][j][1] + (s[i] == '0') * cnt[i + 1][j][1] * pw[s.size() - 1 - i];
				dp[i][j][0] %= MOD;
				dp[i][j][1] %= MOD;
				cnt[i][j][0] += cnt[i + 1][j][0];
				cnt[i][j][0] %= MOD;
				cnt[i][j][1] += cnt[i + 1][j][1];
				cnt[i][j][0] %= MOD;
				if (j)
				{
					dp[i][j][0] += dp[i + 1][j-1][1] + (s[i] == '1') * cnt[i + 1][j-1][1] * pw[s.size() - 1 - i];
					dp[i][j][1] += dp[i + 1][j-1][0] + (s[i] == '0') * cnt[i + 1][j-1][0] * pw[s.size() - 1 - i];
					dp[i][j][0] %= MOD;
					dp[i][j][1] %= MOD;
					cnt[i][j][0] += cnt[i + 1][j-1][1];
					cnt[i][j][0] %= MOD;
					cnt[i][j][1] += cnt[i + 1][j-1][0];
					cnt[i][j][0] %= MOD;
				}
			}
		}
	}
	ce[0] = '0';
	auto r = dfs(0, K, s[0]=='1');
	auto r2 = dfs(0, K-1, s[0] == '1');
	cs[0] = '1';
	ce[0] = '1';
	auto r3 = dfs(0, K, s[0] == '0');
	auto r4 = dfs(0, K-1, s[0] == '0');
	cout << ((r.second + r2.second + r3.second + r4.second) * pw[s.size()] + r.first + r2.first + r3.first + r4.first) % MOD;
}

Compilation message

ljetopica.cpp: In function 'long long int gt(std::string&, std::string&)':
ljetopica.cpp:8:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (i = 0; i < a.size(); i++)
      |              ~~^~~~~~~~~~
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:55:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (i = 0; i < s.size(); i++)
      |              ~~^~~~~~~~~~
ljetopica.cpp:66:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (i == s.size() - 1)
      |       ~~^~~~~~~~~~~~~~~
ljetopica.cpp:76:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   76 |    for (j = 0; j <= s.size()-1-i; j++)
      |                ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22996 KB Output is correct
2 Correct 19 ms 21460 KB Output is correct
3 Correct 18 ms 19924 KB Output is correct
4 Correct 15 ms 18288 KB Output is correct
5 Correct 15 ms 16724 KB Output is correct
6 Correct 13 ms 15060 KB Output is correct
7 Correct 12 ms 13524 KB Output is correct
8 Correct 10 ms 12116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 516 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 23092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22996 KB Output is correct
2 Correct 19 ms 21460 KB Output is correct
3 Correct 18 ms 19924 KB Output is correct
4 Correct 15 ms 18288 KB Output is correct
5 Correct 15 ms 16724 KB Output is correct
6 Correct 13 ms 15060 KB Output is correct
7 Correct 12 ms 13524 KB Output is correct
8 Correct 10 ms 12116 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 516 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 0 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Incorrect 32 ms 23092 KB Output isn't correct
25 Halted 0 ms 0 KB -