Submission #845438

#	Time	Username	Problem	Language	Result	Execution time	Memory
845438		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	125 ms	25936 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;
}


int32_t main()
{
	fastio();

	int n, k;
	cin>>n>>k;
	vector<string> arr[n + 5];
	map<string, vector<int>> ind[N];

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

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

	for (int i = n; i >= 2; i--){
		for (int j = 0; j < k; j++){
			//cout<<i<<sp<<dpold[j]<<endl;
			string a = "";
			for (int l = 1; l < arr[i][j].size(); l++)
				a.pb(arr[i][j][l]);
			for (auto l : ind[i - 1][a])
				dp[l] = add(dp[l], dpold[j]);

			string b = "";
			for (int l = 0; l + 1 < arr[i][j].size(); l++)
				b.pb(arr[i][j][l]);

			if (a == b) continue;
			for (auto l : ind[i - 1][b])
				dp[l] = add(dp[l], dpold[j]);
		}

		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 'int32_t main()':
trener.cpp:51:22: 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]
   51 |    for (int l = 1; l < arr[i][j].size(); l++)
      |                    ~~^~~~~~~~~~~~~~~~~~
trener.cpp:57:26: 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]
   57 |    for (int l = 0; l + 1 < arr[i][j].size(); l++)
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~

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