oj.uz

Submission #845398

# Submission time Handle Problem Language Result Execution time Memory
845398 2023-09-06T13:28:38 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 5580 KB 
#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

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.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 600 KB Output is correct
2 Correct 82 ms 832 KB Output is correct
3 Correct 101 ms 844 KB Output is correct
4 Correct 115 ms 600 KB Output is correct
5 Correct 161 ms 824 KB Output is correct
6 Correct 134 ms 832 KB Output is correct
7 Correct 115 ms 600 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 81 ms 600 KB Output is correct
6 Correct 82 ms 832 KB Output is correct
7 Correct 101 ms 844 KB Output is correct
8 Correct 115 ms 600 KB Output is correct
9 Correct 161 ms 824 KB Output is correct
10 Correct 134 ms 832 KB Output is correct
11 Correct 115 ms 600 KB Output is correct
12 Execution timed out 2008 ms 5580 KB Time limit exceeded
13 Halted 0 ms 0 KB -