Guest User

Untitled

a guest
Aug 8th, 2011
574
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. const int Maxn = 20005;
  7. const int Maxm = 20005;
  8.  
  9. int n, m, p;
  10. int x[Maxn], y[Maxm];
  11. int pthr[Maxn + Maxm], pthc[Maxn + Maxm];
  12.  
  13. int f(int r, int c)
  14. {
  15. return (x[r] + y[c]) % p;
  16. }
  17.  
  18. void findAns(int r1, int c1, int r2, int c2)
  19. {
  20. if (r1 == r2)
  21. for (int j = c1; j <= c2; j++) { pthr[r1 + j] = r1; pthc[r1 + j] = j; }
  22. else if (c1 == c2)
  23. for (int i = r1; i <= r2; i++) { pthr[i + c1] = i; pthc[i + c1] = c1; }
  24. else {
  25. int from1[Maxn + Maxm] = {0};
  26. int from2[Maxn + Maxm] = {0};
  27. int k = (r1 + c1 + r2 + c2) / 2;
  28. from1[c1] = f(r1, c1);
  29. for (int d = r1 + c1 + 1; d <= k; d++)
  30. for (int j = c2; j >= c1; j--)
  31. if (r1 <= d - j && d - j <= r2) {
  32. from1[j] = max(from1[j], from1[j - 1]);
  33. from1[j] += f(d - j, j);
  34. }
  35. from2[c2] = f(r2, c2);
  36. for (int d = r2 + c2 - 1; d >= k; d--)
  37. for (int j = c1; j <= c2; j++)
  38. if (r1 <= d - j && d - j <= r2) {
  39. from2[j] = max(from2[j], from2[j + 1]);
  40. from2[j] += f(d - j, j);
  41. }
  42. int best = -1, besti = 0;
  43. for (int j = c1; j <= c2; j++)
  44. if (r1 <= k - j && k - j <= r2) {
  45. int curbest = from1[j] + from2[j] - f(k - j, j);
  46. if (curbest > best) {
  47. best = curbest; besti = j;
  48. }
  49. }
  50. pthr[k] = k - besti; pthc[k] = besti;
  51. findAns(r1, c1, pthr[k], pthc[k]);
  52. findAns(pthr[k], pthc[k], r2, c2);
  53. }
  54. }
  55.  
  56. int main()
  57. {
  58. scanf("%d %d %d", &n, &m, &p);
  59. for (int i = 0; i < n; i++) scanf("%d", &x[i]);
  60. for (int i = 0; i < m; i++) scanf("%d", &y[i]);
  61. findAns(0, 0, n - 1, m - 1);
  62. int res = 0;
  63. for (int i = 0; i <= n + m - 2; i++)
  64. res += f(pthr[i], pthc[i]);
  65. printf("%d\n", res);
  66. for (int i = 0; i < n + m - 2; i++)
  67. if (pthr[i] == pthr[i + 1]) printf("S");
  68. else printf("C");
  69. printf("\n");
  70. return 0;
  71. }
Add Comment
Please, Sign In to add comment