Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <algorithm>
- #include <math.h>
- using namespace std;
- const int P = 53, MN = 100010;
- const int INF = 1000000007;
- const double eps = (1e-7);
- int n, p, a[MN], b[MN], d[MN][110], t[MN][110];
- main() {
- freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
- //freopen("nails.in", "r", stdin); freopen("nails.out", "w", stdout);
- scanf("%d%d", &n, &p);
- for (int i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- }
- for (int i = 1; i <= p; i++) {
- scanf("%d", &b[i]);
- }
- for (int i = 1; i <= n; i++) {
- int k = -1;
- for (int j = 1; j <= p; j++) {
- while (a[k + 1] <= a[i] - b[j]) k++;
- d[i][j] = d[i][j - 1];
- t[i][j] = -2;
- if (d[i-1][j] > d[i][j]) {
- d[i][j] = d[i-1][j];
- t[i][j] = -1;
- }
- if (k >= 0 && d[i][j] < d[k][j - 1] + 1) {
- d[i][j] = d[k][j - 1] + 1;
- t[i][j] = k;
- }
- //printf ("%d ", d[i][j]);
- }//printf("\n");
- }
- printf ("%d\n", d[n][p]);
- while (n > 0 && p > 0) {
- //printf("%d %d %d\n", n, p, t[n][p]);
- if (t[n][p] >= 0) {
- printf("%d %d\n", p, n);
- n = t[n][p];
- }
- else if (t[n][p] == -1) {
- n--;
- }
- else {
- p--;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment