oj.uz

Submission #891133

# Submission time Handle Problem Language Result Execution time Memory
891133 2023-12-22T08:21:21 Z Hhw48 Martian DNA (BOI18_dna) C++14
0 / 100
 2000 ms 4336 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 4336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4200 KB Output isn't correct
2 Halted 0 ms 0 KB -