oj.uz

Submission #1001676

# Submission time Handle Problem Language Result Execution time Memory
1001676 2024-06-19T06:55:47 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 1419 ms 6800 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];

int f(int l, int r)
{
	if (R[l] >= r) return 1;
  if (dp[l][r] != -1) return dp[l][r];
  dp[l][r] = inf;
  for (int i = l; i <= R[l]; i++)
  {
    dp[l][r] = min(dp[l][r], f(i + 1, r) + 1);
  }
  return dp[l][r];
}
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 i = 0; i < m; i++)
  {
    int l, r;
    cin >> l >> r;
    l++;
		cout << (f(l, r) == inf ? -1 : f(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 41 ms 5848 KB Output is correct
3 Correct 53 ms 5956 KB Output is correct
4 Correct 50 ms 6608 KB Output is correct
5 Correct 46 ms 6404 KB Output is correct
6 Correct 54 ms 6800 KB Output is correct
7 Correct 45 ms 6684 KB Output is correct
8 Correct 60 ms 6640 KB Output is correct
9 Correct 59 ms 6228 KB Output is correct
10 Correct 47 ms 5620 KB Output is correct
11 Correct 39 ms 6008 KB Output is correct
12 Correct 37 ms 5600 KB Output is correct
13 Correct 36 ms 5864 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1419 ms 6536 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 41 ms 5848 KB Output is correct
3 Correct 53 ms 5956 KB Output is correct
4 Correct 50 ms 6608 KB Output is correct
5 Correct 46 ms 6404 KB Output is correct
6 Correct 54 ms 6800 KB Output is correct
7 Correct 45 ms 6684 KB Output is correct
8 Correct 60 ms 6640 KB Output is correct
9 Correct 59 ms 6228 KB Output is correct
10 Correct 47 ms 5620 KB Output is correct
11 Correct 39 ms 6008 KB Output is correct
12 Correct 37 ms 5600 KB Output is correct
13 Correct 36 ms 5864 KB Output is correct
14 Runtime error 1419 ms 6536 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -