abdukodir

Untitled

Sep 12th, 2015
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <math.h>
  4. using namespace std;
  5. const int P = 53, MN = 100010;
  6. const int INF = 1000000007;
  7. const double eps = (1e-7);
  8.  
  9. int n, p, a[MN], b[MN], d[MN][110], t[MN][110];
  10.  
  11. main() {
  12. freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  13. //freopen("nails.in", "r", stdin); freopen("nails.out", "w", stdout);
  14. scanf("%d%d", &n, &p);
  15. for (int i = 1; i <= n; i++) {
  16. scanf("%d", &a[i]);
  17. }
  18. for (int i = 1; i <= p; i++) {
  19. scanf("%d", &b[i]);
  20. }
  21. for (int i = 1; i <= n; i++) {
  22. int k = -1;
  23. for (int j = 1; j <= p; j++) {
  24. while (a[k + 1] <= a[i] - b[j]) k++;
  25. d[i][j] = d[i][j - 1];
  26. t[i][j] = -2;
  27. if (d[i-1][j] > d[i][j]) {
  28. d[i][j] = d[i-1][j];
  29. t[i][j] = -1;
  30. }
  31. if (k >= 0 && d[i][j] < d[k][j - 1] + 1) {
  32. d[i][j] = d[k][j - 1] + 1;
  33. t[i][j] = k;
  34. }
  35. //printf ("%d ", d[i][j]);
  36. }//printf("\n");
  37. }
  38. printf ("%d\n", d[n][p]);
  39. while (n > 0 && p > 0) {
  40. //printf("%d %d %d\n", n, p, t[n][p]);
  41. if (t[n][p] >= 0) {
  42. printf("%d %d\n", p, n);
  43. n = t[n][p];
  44. }
  45. else if (t[n][p] == -1) {
  46. n--;
  47. }
  48. else {
  49. p--;
  50. }
  51. }
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment