Submission #733478

#	Time	Username	Problem	Language	Result	Execution time	Memory
733478		rahulverma	Martian DNA (BOI18_dna)	Java	0 / 100	730 ms	21088 KiB

dna

import java.io.*;
import java.util.*;

public class dna {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// two pointers
		
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int k = s.nextInt();
		int r = s.nextInt();
		int[] freq = new int[k+5];
		int[] req = new int[k+5];
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = s.nextInt();
			freq[arr[i]]++;
		}
		for(int i = 0; i < r; i++) {
			int v1 = s.nextInt();
			int v2 = s.nextInt();
			req[v1] += v2;
		}
		for(int i = 0; i < k + 5; i++) {
			if(freq[i] < req[i]) {
				System.out.println("impossible");
				return;
			}
		}
		
		int p1 = 0;
		int p2 = n - 1;
		while(p1 < p2) {
			boolean works = false;
			if(freq[arr[p1]] - 1 >= req[arr[p1]]) {
				freq[arr[p1]]--;
				p1++;
				works = true;
			}
			if(freq[arr[p2]] - 1 >= req[arr[p2]]) {
				freq[arr[p2]]--;
				p2--;
				works = true;
			}
			if(!works) {
				System.out.println(p2 - p1 + 1);
				return;
			}
		}
		
	}

}

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