oj.uz

Submission #635438

# Submission time Handle Problem Language Result Execution time Memory
635438 2022-08-26T09:12:27 Z NothingXD Dabbeh (INOI20_dabbeh) C++17
25 / 100
 169 ms 104880 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 500 + 10;
const int maxa = 5e5 + 10;
const int inf = 1e9;
const int alpha = 26;

int n, q, dp[maxn][maxn], trie[maxa][alpha], vercnt;
string s;

void add(string &s){
	int v = 0;
	for (auto c: s){
		int x = c - 'a';
		if (trie[v][x] == -1) trie[v][x] = ++vercnt;
		v = trie[v][x];
	}
}

bool find(int l, int r){
	int v = 0;
	for (int i = l; i <= r; i++){
		int x = s[i] - 'a';
		if (trie[v][x] == -1) return false;
		v = trie[v][x];
	}
	return true;
}

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

	memset(trie, -1, sizeof trie);

	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		string s; cin >> s;
		add(s);
	}

	cin >> s;

	int sz = s.size();

	for (int i = sz-1; ~i; i--){
		for (int j = i; j < sz; j++){
			dp[i][j] = inf;
			if (find(i, j)){
				dp[i][j] = 1;
				continue;
			}
			for (int k = i; k < j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
			}
		}
	}

	while(q--){
		int l, r; cin >> l >> r;
		cout << (dp[l][r-1] == inf? -1: dp[l][r-1]) << '\n';
	}

	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51156 KB Output is correct
2 Correct 82 ms 54268 KB Output is correct
3 Correct 91 ms 55100 KB Output is correct
4 Correct 104 ms 55440 KB Output is correct
5 Correct 112 ms 55660 KB Output is correct
6 Correct 115 ms 55692 KB Output is correct
7 Correct 117 ms 55932 KB Output is correct
8 Correct 112 ms 55692 KB Output is correct
9 Correct 137 ms 55628 KB Output is correct
10 Correct 131 ms 55312 KB Output is correct
11 Correct 160 ms 55472 KB Output is correct
12 Correct 164 ms 55312 KB Output is correct
13 Correct 169 ms 55348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 104880 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 19 ms 51156 KB Output is correct
2 Correct 82 ms 54268 KB Output is correct
3 Correct 91 ms 55100 KB Output is correct
4 Correct 104 ms 55440 KB Output is correct
5 Correct 112 ms 55660 KB Output is correct
6 Correct 115 ms 55692 KB Output is correct
7 Correct 117 ms 55932 KB Output is correct
8 Correct 112 ms 55692 KB Output is correct
9 Correct 137 ms 55628 KB Output is correct
10 Correct 131 ms 55312 KB Output is correct
11 Correct 160 ms 55472 KB Output is correct
12 Correct 164 ms 55312 KB Output is correct
13 Correct 169 ms 55348 KB Output is correct
14 Runtime error 75 ms 104880 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -