Submission #1098726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098726		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	177 ms	10384 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int N = 2005;
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int X = 100;


map<int,int> mp;
int cnt;

void add(int x){
	if(!mp.count(x))return;
	mp[x]--;
	if(mp[x] == 0)cnt--;
}

void rem(int x){
	if(!mp.count(x))return;
	if(mp[x] == 0)cnt++;
	mp[x]++;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n, k, r;
	cin>>n>>k>>r;
	int A[n];
	for(int i = 0;i < n;i++)cin>>A[i];
	//map<int, int> mp;
	cnt = r;
	while(r--){
		int x, y;
		cin>>x>>y;
		mp[x] = y;
	}
	int mr = -1;
	int ans = INF;
	for(int i =0;i < n;i++){
		while(mr + 1 < n && cnt)add(A[++mr]);
		if(!cnt)ans = min(ans, mr - i + 1);
		rem(A[i]);
	}
	if(ans >= INF)cout<<"impossible";
	else cout<<ans;
}	

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