Submission #635438

#	Time	Username	Problem	Language	Result	Execution time	Memory
635438		NothingXD	Dabbeh (INOI20_dabbeh)	C++17	25 / 100	169 ms	104880 KiB

Main

#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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50