Submission #1128864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128864		Alihan_8	Martian DNA (BOI18_dna)	C++20	100 / 100	97 ms	12872 KiB

dna

#include <bits/stdc++.h>

using namespace std;

signed main(){
	int n, k, r; cin >> n >> k >> r;
	
	vector <int> d(n);
	
	for ( auto &u: d ) cin >> u;
	
	vector <int> b(r), q(r);
	
	for ( int i = 0; i < r; i++ ){
		cin >> b[i] >> q[i];
	}
	
	vector <vector<int>> p(k);
	vector <int> it(k, -1);
	
	for ( int i = 0; i < n; i++ ) p[d[i]].push_back(i);
	
	int mx = 0;
	
	for ( int i = 0; i < r; i++ ){
		int j = b[i];
		
		if ( (int)p[j].size() < q[i] ) return cout << "impossible\n", 0;
		
		it[j] = q[i] - 1; 
		mx = max(mx, p[j][it[j]]);
	}
	
	int opt = mx + 1;
	
	for ( int i = 0; i < n; i++ ){
		int j = d[i];
		
		if ( it[j] != -1 ){
			if ( ++it[j] == (int)p[j].size() ) break;
			
			mx = max(mx, p[j][it[j]]);
		}
		
		opt = min(opt, mx - i);
	}
	
	cout << opt << '\n';
}

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