Submission #891033

#	Time	Username	Problem	Language	Result	Execution time	Memory
891033		Hhw48	Martian DNA (BOI18_dna)	C++14	0 / 100	2086 ms	4336 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k,r;
	cin>>n>>k>>r;
	string s="";
	int tmp=0,tmp2=0;
	for(int i=0; i<n; i++){
		char x;
		cin>>x;
		s += x;
	}
	multiset<int>mset;
	unordered_set <int> uset;
	vector<pii>vec;
	for(int i=0; i<r; i++){
		int a,b;
		cin>>a>>b;
		vec.pb({a,b});
		tmp += b;
		uset.insert(a);
	}
	for(int i=0; i<n; i++){
		if(uset.count(s[i]-'0')==1){
			tmp2++;
		}
	}
	if(tmp2<tmp){
		cout<<"impossible";
		return 0;
	}
	for(int i=tmp; i<n; i++){
		for(int x=0; x<n-i; x++){
			int idx=x;
			while(idx<x+i){
				if(uset.count(s[idx]-'0')==1){
					mset.insert(s[idx]-'0');
				}
				idx++;
			}
			bool flag=false;
			for(int j=0; j<r; j++){
				if(mset.count(vec[j].fi)<vec[j].se)flag=true;
			}
			if(flag==0){
				cout<<i;
				exit(0);
			}
			mset.clear();
		}
	}
}

Compilation message (stderr)

dna.cpp: In function 'int32_t main()':
dna.cpp:50:29: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   50 |     if(mset.count(vec[j].fi)<vec[j].se)flag=true;
      |                             ^

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