oj.uz

Submission #891575

# Submission time Handle Problem Language Result Execution time Memory
891575 2023-12-23T08:51:29 Z jellybean Martian DNA (BOI18_dna) C++17
16 / 100
 2000 ms 12488 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n,k,r; cin>>n>>k>>r;
	int arr[n];
	map<int,int>m;
	map<int,int>req;
	set<int>s;
	vector<int>v;
	for(int i=0; i<n; i++) cin>>arr[i];
	for(int i=0; i<r; i++){
		int a,b; cin>>a>>b;
		req[a]=b;
		s.insert(a);
		v.push_back(a);
	}
	int st=0,ans=LLONG_MAX;
	/*for(int i=0; i<n; i++){
		if(req.find(arr[i])!=req.end()) m[arr[i]]++;
		if(m[arr[i]]>=req[arr[i]] and s.find(arr[i])!=s.end()) s.erase(arr[i]);
		while(s.empty()){
			ans=min(ans,i-st+1);
			if(req.find(arr[st])!=req.end()){
				m[arr[st]]--;
				if(m[arr[st]]<req[arr[st]]) s.insert(arr[st]);
			}
			st++;
		}
	}
	if(ans==LLONG_MAX) cout<<"impossible";
	else cout<<ans;*/
	
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			for(int x=i; x<=j; x++){
				if(req.find(arr[x])!=req.end()) m[arr[x]]++;
				if(m[arr[x]]>=req[arr[x]] and s.find(arr[x])!=s.end()) s.erase(arr[x]);
			}
			if(s.empty()) ans=min(ans,j-i+1);
			m.clear();
			for(auto x: v)s.insert(x);
		}
	}
	if(ans==LLONG_MAX) cout<<"impossible";
	else cout<<ans;
	
	return 0;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:21:6: warning: unused variable 'st' [-Wunused-variable]
   21 |  int st=0,ans=LLONG_MAX;
      |      ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 14 ms 456 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 12 ms 464 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 15 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 6 ms 344 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 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 2055 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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