oj.uz

Submission #890955

# Submission time Handle Problem Language Result Execution time Memory
890955 2023-12-22T05:35:55 Z AccountName Martian DNA (BOI18_dna) C++14
0 / 100
 22 ms 3272 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int dna_len, alphabet_size, req_nucleobase_no;
    cin >> dna_len >> alphabet_size >> req_nucleobase_no;
    
    int dna[dna_len];
    for(int i = 0; i < dna_len; i++)
    {
		cin >> dna[i];
	}
	int req_nucleobase[alphabet_size];
    int extra_nucleobases[alphabet_size];
    for(int i = 0; i < alphabet_size; i++)
    {
		req_nucleobase[i] = -1;
		extra_nucleobases[i] = 0;
	}
    for(int i = 0; i < req_nucleobase_no; i++)
    {
		int nucleobase;
		cin >> nucleobase;
		cin >> req_nucleobase[nucleobase];
	}
    
    int no_of_req_met, shortest_len = 0;
    int left = 0;
    for(int right = 0; right < dna_len; right++)
    {
		if(req_nucleobase[dna[right]] > 0)
		{
			req_nucleobase[dna[right]]--;
			if(req_nucleobase[dna[right]] == 0)
			{
				no_of_req_met++;
			}
		}
		else
		{
			extra_nucleobases[dna[right]]++;
		}
		while(extra_nucleobases[dna[left]] > 0 and left <= right)
		{
			left++;
			extra_nucleobases[dna[left]]--;
		}
		
		if(no_of_req_met == req_nucleobase_no)
		{
			int curr_len = right - left + 1;
			shortest_len = (shortest_len == 0)? curr_len : min(curr_len, shortest_len);
		}
	}
	
    if(no_of_req_met < req_nucleobase_no)
    {
		cout << "impossible";
	}
	else
	{
		cout << shortest_len;
	}
    
	return 0;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:61:5: warning: 'no_of_req_met' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     if(no_of_req_met < req_nucleobase_no)
      |     ^~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

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