oj.uz

Submission #733478

# Submission time Handle Problem Language Result Execution time Memory
733478 2023-04-30T22:50:43 Z rahulverma Martian DNA (BOI18_dna) Java 11
0 / 100
 730 ms 21088 KB 
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.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

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