Submission #1172008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172008		bahaktl	Martian DNA (BOI18_dna)	C++20	16 / 100	2095 ms	1096 KiB

dna

#include <bits/stdc++.h>   
using namespace std;
#define int long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int inf=1e16;
const int N=1e5+10;
const int mod=1e9+7;
int n,k,r;
int a[N];
vector<pair<int,int>>v;

bool check(int l,int r) {
	bool ok=true;
	map<int,int>mp;
	//cout<<l<<' '<<r<<"\n";
	for(int i=l;i<=r;i++) {
		mp[a[i]]++;
		//cout<<a[i]<<' ';
	}
	//cout<<"\n";
	for(auto [t,q]:v) {
		if(mp[t]<q) {
			ok=false;
			break;
		}
	}
	return ok;
}

signed main () {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,k,r;
	cin>>n>>k>>r;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	while(r--) {
		int t,q;
		cin>>t>>q;
		v.pb({t,q});
	}
	int len=inf;
	for(int l=1;l<=n;l++) {
		for(int r=l;r<=n;r++) {
			if(check(l,r)) {
				len=min(r-l+1,len);
				break;
			}
		}
	}
	if(len==inf) {
		cout<<"impossible";
		return 0;
	}
	cout<<len;
}   

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