Submission #845364

#	Time	Username	Problem	Language	Result	Execution time	Memory
845364		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	115 ms	6480 KiB

trener

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 3e5 + 5;

vector<vector<string>> play;
map<string,int> dp;

int main() {
	fast
	int N, K;
	cin >> N >> K;

	play = vector<vector<string>>(N+1, vector<string>());
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < K; j++) {
			string s;
			cin >> s;
			play[i].push_back(s);
		}
	}

	for (int i = 0; i < play[N].size(); i++) {
		string s1 = play[N][i];
		s1[0] = 'A';
		s1 = s1 + 'A';
		string s2 = play[N][i];
		s2[play[N][i].length() - 1] = 'A';
		s2 = 'A' + s2;
		dp[s1]++;
		if (s1 != s2)
			dp[s2]++;
	}

	for (int i = N-1; i >= 1; i--) {
		map<string,int> new_dp;
		for (int s1 = 0; s1 < play[i].size(); s1++) {
			string str1 = play[i][s1];
			str1 = 'A' + str1 + 'A';


			string ns1 = play[i][s1];
			string ns2 = play[i][s1];
			ns1[0] = 'A';
			ns1 = ns1 + 'A';
			ns2[i - 1] = 'A';
			ns2 = 'A' + ns2;
			new_dp[ns1] = (new_dp[ns1] + dp[str1]) % MOD;
			if (ns1 != ns2)
				new_dp[ns2] = (new_dp[ns2] + dp[str1]) % MOD;
		}
		dp = new_dp;
	}

	int ans = 0;
	for (auto u : dp)
		ans = (ans + u.s) % MOD;
	cout << ans << "\n";
}

Compilation message (stderr)

trener.cpp: In function 'int main()':
trener.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 0; i < play[N].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
trener.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int s1 = 0; s1 < play[i].size(); s1++) {
      |                    ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55