Submission #890908

#	Time	Username	Problem	Language	Result	Execution time	Memory
890908		shoryu386	Martian DNA (BOI18_dna)	C++17	100 / 100	117 ms	12952 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define int long long

main(){
	int n, k, req; cin >> n >> k >> req;
	
	int arr[n];
	for (int x = 0; x < n; x++){
		cin >> arr[x];
	}
	
	int ans = INT_MAX; unordered_set<int> unfulfilled;
	unordered_map<int, int> requires; int a, b;
	for (int x = 0; x < req; x++){
		cin >> a >> b;
		requires[a] = b;
		unfulfilled.insert(a);
	}
	
	int l = 0;
	for (int r = 0; r < n; r++){
		if (requires.count(arr[r])){
			requires[arr[r]]--;
			if (requires[arr[r]] <= 0) unfulfilled.erase(arr[r]);
		}
		
		while (l <= r && unfulfilled.size() == 0){
			if (requires.count(arr[l]) && requires[arr[l]] >= 0){
				break;
			}
			
			if (requires.count(arr[l])) requires[arr[l]]++;
			l++;
		}
		
		if (unfulfilled.size() == 0) ans = min(ans, r-l+1);
	}
	
	if (ans != INT_MAX) cout << ans;
	else cout << "impossible";
}

Compilation message (stderr)

dna.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main(){
      | ^~~~

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