Submission #483612

#	Time	Username	Problem	Language	Result	Execution time	Memory
483612		ntabc05101	Ljetopica (COI19_ljetopica)	C++14	100 / 100	81 ms	23260 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const int mod = 1e9 + 7;
const int mxN = 1005;

int n, k;
string str;
//int pw2[mxN];

template<class U, class T>
void add(U &a, T b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	}
}

int sol(string &A) {
	if (!A[0]) {
		return 0;
	}
	int dp[n][k + 1][2];
	long long dp2[n][k + 1][2];

	int res = 0;
	for (bool e: {0, 1}) {
		memset(dp, 0, sizeof(dp));
		memset(dp2, 0, sizeof(dp2));
		dp[0][0][1] = 1;
		dp2[0][0][1] = 1;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j <= k; j++) {
				for (int f: {0, 1}) {
					if (j + f > k) {
						continue;
					}
					int g = str[i] ^ ((j + f) & 1);
					add(dp[i + 1][j + f][0], dp[i][j][0]);
					add(dp2[i + 1][j + f][0], (dp2[i][j][0] * 2 + dp[i][j][0] * g) % mod);
					if (g < A[i + 1]) {
						add(dp[i + 1][j + f][0], dp[i][j][1]);
						add(dp2[i + 1][j + f][0], (dp2[i][j][1] * 2 + dp[i][j][1] * g) % mod);
					}
					else {
						if (g == A[i + 1]) {
							add(dp[i + 1][j + f][1], dp[i][j][1]);
							add(dp2[i + 1][j + f][1], (dp2[i][j][1] * 2 + dp[i][j][1] * g) % mod);
						}
					}
					//cout << i + 1 << " " << j + f << " " << dp[i + 1][j + f][0] << " " << dp[i + 1][j + f][1] << "\n";
				}
			}
		}
		add(res, dp2[n - 1][k][0]);
		add(res, dp2[n - 1][k][1]);
		for (auto& c: str) {
			c ^= 1;
		}
	}

	//cout << res << "\n";
	return res;
}

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  else {
    if (fopen(taskname".in", "r")) {
      freopen(taskname".in", "r", stdin);
      freopen(taskname".out", "w", stdout);
    }
  }

  cin.tie(0)->sync_with_stdio(0);
	
	cin >> n >> k;
	/*pw2[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw2[i] = pw2[i - 1] * 2 % mod;
	}*/
	cin >> str;
	string A, B; cin >> A >> B;
	for (auto &c: A) {
		c -= '0';
	}
	for (auto &c: B) {
		c -= '0';
	}

	int i;
	for (i = A.size() - 1; (~i) && !A[i]; i--) {
		A[i] = 1;
	}
	A[i] = 0;

	//for (auto &c: A) cout << char(c + '0'); cout << "\n";

	for (auto &c: str) {
		c = (c == 'R');
	}

	cout << (sol(B) - sol(A) + mod) % mod << "\n";

  return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'int sol(std::string&)':
ljetopica.cpp:29:12: warning: unused variable 'e' [-Wunused-variable]
   29 |  for (bool e: {0, 1}) {
      |            ^
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:75:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |       freopen(taskname".in", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:76:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |       freopen(taskname".out", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61