Advertisement
Guest User

Untitled

a guest
Apr 19th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.30 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int arr[101][101],dp[101][101][11];
  6.  
  7. int main()
  8. {
  9. int n,m,k;
  10. string s;
  11. char c;
  12. cin>>n>>m>>k;
  13. k++;
  14. for (int i=1;i<=n;i++)
  15. for (int j=1;j<=m;j++)
  16. {
  17. cin>>c;
  18. arr[n-i+1][j]=c-'0';
  19. }
  20. for (int i=1;i<=m;i++)
  21. dp[1][i][arr[1][i]%k]=arr[1][i];
  22. for (int i=1;i<n;i++)
  23. {
  24. for (int j=2;j<m;j++)
  25. {
  26. for (int t=0;t<k;t++)
  27. {
  28. int to = (dp[i][j][t] + arr[i+1][j+1]) % k;
  29.  
  30. if(dp[i+1][j+1][to] < dp[i][j][t] + arr[i+1][j+1])
  31. dp[i+1][j+1][to] = dp[i][j][t] + arr[i+1][j+1],
  32. from[i + 1][j + 1][(dp[i][j][t] + arr[i+1][j+1])%k] = -1;
  33.  
  34. if(dp[i+1][j+1][to] < dp[i][j][t] + arr[i+1][j+1])
  35. dp[i+1][j+1][to] = dp[i][j][t] + arr[i+1][j+1],
  36. from[i + 1][j + 1][(dp[i][j][t] + arr[i+1][j+1])%k] = -1;
  37.  
  38.  
  39. dp[i+1][j-1][(dp[i][j][t]+arr[i+1][j-1])%k]=max(dp[i+1][j-1][(dp[i][j][t]+arr[i+1][j-1])%k], dp[i][j][t]+arr[i+1][j-1]);
  40. }
  41. }
  42. }
  43. int ma=-1,indma=0;
  44. for (int i=1;i<=m;i++)
  45. {
  46. if (ma<dp[n][i][0])
  47. {
  48. ma=dp[n][i][0];
  49. indma=i;
  50. }
  51. }
  52. if (indma==0||ma==0)
  53. cout<<-1;
  54. else
  55. {
  56. cout<<ma<<endl;
  57. int i=n;
  58. int kcur=0;
  59. while (i-1)
  60. {
  61. if (indma==1)
  62. indma=2, s.push_back('L'), kcur = (kcur + k - arr[i][indma] % k) % k;
  63. else if (indma==m)
  64. indma=m-1, s.push_back('R'), kcur = (kcur + k - arr[i][indma] % k) % k;
  65. else
  66. {
  67. // cerr << "sdf : " << i << endl;
  68. int newk = (kcur + k - arr[i][indma] % k) % k;
  69. if (dp[i-1][indma-1][newk] == dp[i][indma][kcur]-arr[i][indma])
  70. indma--, s.push_back('R');
  71. else indma++, s.push_back('L');
  72. kcur = newk;
  73. }
  74. i--;
  75. }
  76. cout<<indma<<endl;
  77. while (s.size())
  78. {
  79. auto c=s.back();
  80. s.pop_back();
  81. cout<<c;
  82. }
  83. }
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement