oj.uz

Submission #1001688

# Submission time Handle Problem Language Result Execution time Memory
1001688 2024-06-19T07:00:38 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 1638 ms 6740 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

const int MXN = 3e5 + 5;
const int mod = 1e9 + 7;
int b1, b2;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[505][505];
int R[505];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
	for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) dp[i][j] = -1;
  int k, m;
  cin >> k >> m;
  string t[k];
  for (int i = 0; i < k; i++) cin >> t[i];
  string s;
  cin >> s;
  int n = s.length();
  s = "#" + s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			for (int l = i; l <= n; l++)
			{
				if (s[l] != t[j][l - i]) break;
				R[i] = max(R[i], l);
			}
		}
	}
	for (int sz = 1; sz <= n; sz++)
	{
		for (int i = 1; i + sz - 1 <= n; i++)
		{
			int j = i + sz - 1;
			if (R[i] >= j) dp[i][j] = 1;
			else dp[i][j] = inf;
			for (int k = i; k < j; k++)
			{
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		}
	}
  for (int i = 0; i < m; i++)
  {
    int l, r;
    cin >> l >> r;
    l++;
		cout << (dp[l][r] == inf ? -1 : dp[l][r]) << '\n';
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 38 ms 5728 KB Output is correct
3 Correct 46 ms 5972 KB Output is correct
4 Correct 74 ms 6484 KB Output is correct
5 Correct 63 ms 6224 KB Output is correct
6 Correct 70 ms 6740 KB Output is correct
7 Correct 81 ms 6736 KB Output is correct
8 Correct 71 ms 6716 KB Output is correct
9 Correct 66 ms 6172 KB Output is correct
10 Correct 68 ms 5712 KB Output is correct
11 Correct 65 ms 6168 KB Output is correct
12 Correct 60 ms 5596 KB Output is correct
13 Correct 60 ms 5864 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1638 ms 6540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 38 ms 5728 KB Output is correct
3 Correct 46 ms 5972 KB Output is correct
4 Correct 74 ms 6484 KB Output is correct
5 Correct 63 ms 6224 KB Output is correct
6 Correct 70 ms 6740 KB Output is correct
7 Correct 81 ms 6736 KB Output is correct
8 Correct 71 ms 6716 KB Output is correct
9 Correct 66 ms 6172 KB Output is correct
10 Correct 68 ms 5712 KB Output is correct
11 Correct 65 ms 6168 KB Output is correct
12 Correct 60 ms 5596 KB Output is correct
13 Correct 60 ms 5864 KB Output is correct
14 Runtime error 1638 ms 6540 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -