Skip to content

Instantly share code, notes, and snippets.

@banthar
Created October 4, 2012 19:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save banthar/3835990 to your computer and use it in GitHub Desktop.
Save banthar/3835990 to your computer and use it in GitHub Desktop.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
try (final Scanner in = new Scanner(System.in)) {
// wczytywanie:
final int n = in.nextInt();
final int k = in.nextInt() + 1;
final boolean[][] grzyb = new boolean[n][2];
final int l = in.nextInt();
final int p = in.nextInt();
for (int i = 0; i < l; i++)
grzyb[in.nextInt() - 1][0] = true;
for (int i = 0; i < p; i++)
grzyb[in.nextInt() - 1][1] = true;
// pierwszy płotek:
final int[][] skok = new int[n][k];
for (int i = 0; i < k; i++)
skok[0][i] = grzyb[0][0] ? 1 : 0;
for (int i = 1; i < k; i++)
skok[0][i] += grzyb[0][1] ? 1 : 0;
// następne płotki:
for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++) {
int a = skok[i - 1][j] + (grzyb[i][j % 2] ? 1 : 0);
int b;
if (j > 0)
b = skok[i - 1][j - 1] + (grzyb[i][0] ? 1 : 0)
+ (grzyb[i][1] ? 1 : 0);
else
b = 0;
skok[i][j] = Math.max(a, b);
}
}
// wynik:
System.out.println(skok[n - 1][k - 1]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment