oj.uz

Submission #44504

# Submission time Handle Problem Language Result Execution time Memory
44504 2018-04-02T17:32:55 Z MatheusLealV Mate (COCI18_mate) C++17
0 / 100
 111 ms 65040 KB 
#include <bits/stdc++.h>
#define N 2005
#define mod (1000000000 + 7)
using namespace std;
typedef long long ll;

string s;

int n, q, qtd[30][N];

ll dp[30][30][N], ch[N][N];

vector<int> pos[30];

ll choose(int a, int b)
{
	if(a == b || b == 0) return 1;

	if(b == 1) return a;

	if(b > a) return 0;

	if(ch[a][b] != -1) return ch[a][b];

	return ch[a][b] = (choose(a - 1, b - 1) + choose(a - 1, b))%mod;
}

void solve(int a, int b)
{
	for(int len = 1; len <= n; len ++)
	{
		for(int i = 0; i < pos[a].size(); i++)
		{
			int x = pos[a][i];

			dp[len][a][b] += ((ll)qtd[b][x + 1] * choose(x - 1, len - 2))%mod;

			dp[len][a][b] %= mod;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>s;

	n = s.size();

	for(int c = 0; c < 30; c++)
		for(int i = n; i >= 1; i--)
			qtd[c][i] = qtd[c][i + 1] + (s[i - 1] - 'a' == c);

	for(int i = 1; i <= n; i++) pos[ s[i - 1] - 'a'].push_back(i);

	memset(ch, -1, sizeof ch);

	for(int a = 0; a < 30; a++)
		for(int b = 0; b < 30; b++)
			solve(a, b);
		
	cin>>q;

	while(q--)
	{
		int l; string aux;

		cin>>l>>aux;

		int a = aux[0] - 'a', b = aux[1] - 'a';

		cout<<dp[l][a][b]<<"\n";
	}
}

Compilation message

mate.cpp: In function 'void solve(int, int)':
mate.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pos[a].size(); i++)
                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 60 ms 64212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 75 ms 64304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 61 ms 64308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 61 ms 64428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 61 ms 64476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 61 ms 64492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 60 ms 64588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 110 ms 64932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 111 ms 65040 KB Execution killed with signal 11 (could be triggered by violating memory limits)