Submission #826610

#	Time	Username	Problem	Language	Result	Execution time	Memory
826610		serifefedartar	Martian DNA (BOI18_dna)	C++17	68 / 100	324 ms	1048576 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<vector<int>> pref;
vector<int> DNA;
int main() {
	fast
	int N, K, R;
	cin >> N >> K >> R;

	DNA = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> DNA[i];

	pref = vector<vector<int>>(R, vector<int>(N+1, 0));
	vector<pair<int,int>> req(R);
	for (int i = 0; i < R; i++)
		cin >> req[i].f >> req[i].s;

	for (int i = 1; i <= N; i++) {
		for (int ch = 0; ch < R; ch++)
			pref[ch][i] = pref[ch][i-1] + (DNA[i] == req[ch].f);
	}

	int res = 1e7;
	for (int i = 1; i <= N; i++) {
		int ans = 1e7;
		for (int ch = 0; ch < R; ch++) {
			if (pref[ch][i] < req[ch].s)	 {
				ans = -1;
				break;
			}

			int q = upper_bound(pref[ch].begin(), pref[ch].end(), pref[ch][i] - req[ch].s) - pref[ch].begin() - 1;
			ans = min(ans, q);
		}

		if (ans == -1)
			continue;
		else
			res = min(res, i-ans+1);
	}

	if (res == 1e7)
		cout << "impossible\n";
	else
		cout << res-1 << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 0 / 32