Submission #1128859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128859		Alihan_8	Martian DNA (BOI18_dna)	C++20	68 / 100	2095 ms	12868 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);
	
	for ( int i = 0; i < n; i++ ) p[d[i]].push_back(i);
	
	int opt = n + 1;
	
	for ( int i = 0; i < n; i++ ){
		for ( int x = 0; x < r; x++ ){
			int j = b[x];
			
			while ( it[j] < (int)p[j].size() && p[j][it[j]] < i ) it[j]++;
		}
		
		int mx = 0, bad = 0;
		
		for ( int j = 0; j < r; j++ ){
			int nxt = it[b[j]] + q[j];
			
			if ( nxt > (int)p[b[j]].size() ){
				bad = 1; break;
			}
			
			mx = max(mx, p[b[j]][nxt - 1]);
		}
		
		if ( !bad ) opt = min(opt, mx - i + 1);
	}
	
	if ( opt == n + 1 ) return cout << "impossible\n", 0;
	
	cout << opt << '\n';
}

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