oj.uz

Submission #845300

# Submission time Handle Problem Language Result Execution time Memory
845300 2023-09-06T13:05:04 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 18512 KB 
#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++)
		dp[play[N][i]]++;

	for (int i = N-1; i >= 1; i--) {
		map<string,int> new_dp;
		for (int s1 = 0; s1 < play[i].size(); s1++) {
			for (char ch = 'a'; ch <= 'z'; ch++) {
				string str1 = play[i][s1];
				new_dp[str1] = (new_dp[str1] + dp[str1 + ch]) % MOD;
				if (str1 + ch != ch + str1)
					new_dp[str1] = (new_dp[str1] + dp[ch + str1]) % MOD;
			}
		}
		dp = new_dp;
	}

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

Compilation message

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:34: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]
   34 |   for (int s1 = 0; s1 < play[i].size(); s1++) {
      |                    ~~~^~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1884 KB Output is correct
2 Correct 102 ms 1716 KB Output is correct
3 Correct 104 ms 1624 KB Output is correct
4 Correct 39 ms 600 KB Output is correct
5 Correct 94 ms 1596 KB Output is correct
6 Correct 107 ms 1716 KB Output is correct
7 Correct 41 ms 856 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 114 ms 1884 KB Output is correct
6 Correct 102 ms 1716 KB Output is correct
7 Correct 104 ms 1624 KB Output is correct
8 Correct 39 ms 600 KB Output is correct
9 Correct 94 ms 1596 KB Output is correct
10 Correct 107 ms 1716 KB Output is correct
11 Correct 41 ms 856 KB Output is correct
12 Execution timed out 2037 ms 18512 KB Time limit exceeded
13 Halted 0 ms 0 KB -