Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- using namespace std;
- const int INF = (int)1e6;
- int m = 1010;
- int del, k;
- int n;
- int it1, it2;
- int a[55];
- int dp[1010][52][52][3];
- int ans[55][2];
- int main()
- {
- scanf("%d%d", &del, &k);
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- scanf("%d", &a[i]);
- for (int i = 0; i < m; i++)
- for (int j = 0; j <= n; j++)
- for (int h = 0; h <= n; h++)
- dp[i][j][h][0] = INF;
- dp[0][0][0][0] = 0;
- for (int tm = 0; tm < m; tm++)
- {
- while (it1 < n && a[it1] - del <= tm)
- it1++;
- while (it2 < n && a[it2] <= tm)
- it2++;
- for (int frst = 0; frst <= it1; frst++)
- for (int scnd = it2; scnd <= frst; scnd++)
- {
- if (dp[tm][frst][scnd][0] == INF)
- continue;
- if (dp[tm + 1][frst][scnd][0] > dp[tm][frst][scnd][0])
- {
- dp[tm + 1][frst][scnd][0] = dp[tm][frst][scnd][0];
- dp[tm + 1][frst][scnd][1] = frst;
- dp[tm + 1][frst][scnd][2] = scnd;
- }
- int w = dp[tm][frst][scnd][0] + 1;
- if (k >= it1 - scnd)
- {
- if (dp[tm + 1][it1][frst][0] > w)
- {
- dp[tm + 1][it1][frst][0] = w;
- dp[tm + 1][it1][frst][1] = frst;
- dp[tm + 1][it1][frst][2] = scnd;
- }
- }
- else
- {
- for (int i = max( 0, k - (it1 - frst) ); i <= min(k, frst - scnd) ; i++)
- {
- if (dp[tm + 1][frst + k - i][scnd + i][0] > w)
- {
- dp[tm + 1][frst + k - i][scnd + i][0] = w;
- dp[tm + 1][frst + k - i][scnd + i][1] = frst;
- dp[tm + 1][frst + k - i][scnd + i][2] = scnd;
- }
- }
- }
- }
- }
- m--;
- if (dp[m][n][n][0] == INF)
- {
- printf("-1\n");
- return 0;
- }
- printf("%d\n", dp[m][n][n][0]);
- int f = n, s = n;
- for (; m > 0; m--)
- {
- int nf = dp[m][f][s][1];
- int ns = dp[m][f][s][2];
- for (int i = nf; i < f; i++)
- ans[i][0] = m - 1;
- for (int i = ns; i < s; i++)
- ans[i][1] = m - 1;
- f = nf;
- s = ns;
- }
- for (int i = 0; i < n; i++)
- printf("%d %d\n", ans[i][0], ans[i][1]);
- cin >> n;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement