Submission #845398

#	Time	Username	Problem	Language	Result	Execution time	Memory
845398		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	2008 ms	5580 KiB

trener

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 2005
#define int long long

const int modulo = 1e9 + 7;


int dp[N], dpold[N];

int add(int a, int b){
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}



int contains(string &a, string &b){
	string tmp = b + "$" + a;
	vector<int> p(tmp.size(), 0);
	for (int i = 1; i < tmp.size(); i++){
		int prv = i - 1;
		while(prv >= 0){
			if (tmp[p[prv]] == tmp[i]){
				p[i] = p[prv] + 1;	
				break;
			} 
			else{
				prv = p[prv] - 1;
			}
		}
		if (p[i] == b.size()) return 1;
	}
	return 0;
}

int32_t main()
{
	fastio();

	int n, k;
	cin>>n>>k;
	vector<string> arr[n + 5];
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= k; j++)
		{
			string tmp;
			cin>>tmp;
			arr[i].pb(tmp);
		}
	}

	for (int i = 0; i <= k; i++){
		dpold[i] = 1;
	}

	for (int i = n - 1; i >= 1; i--){
		for (int j = 0; j < k; j++){
			for (int l = 0; l < k; l++){
				if (contains(arr[i + 1][l], arr[i][j])) dp[j] = add(dp[j], dpold[l]);
			}
		}

		for (int j = 0; j < k; j++)
			dpold[j] = dp[j], dp[j] = 0;
	}

	int ans = 0;
	for (int i = 0; i < k; i++)
		ans = add(ans, dpold[i]);
	cout<<ans<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

Compilation message (stderr)

trener.cpp: In function 'long long int contains(std::string&, std::string&)':
trener.cpp:28:20: 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]
   28 |  for (int i = 1; i < tmp.size(); i++){
      |                  ~~^~~~~~~~~~~~
trener.cpp:39:12: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if (p[i] == b.size()) return 1;

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