Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int arr[101][101],dp[101][101][11];
- int main()
- {
- int n,m,k;
- string s;
- char c;
- cin>>n>>m>>k;
- k++;
- for (int i=1;i<=n;i++)
- for (int j=1;j<=m;j++)
- {
- cin>>c;
- arr[n-i+1][j]=c-'0';
- }
- for (int i=1;i<=m;i++)
- dp[1][i][arr[1][i]%k]=arr[1][i];
- for (int i=1;i<n;i++)
- {
- for (int j=2;j<m;j++)
- {
- for (int t=0;t<k;t++)
- {
- int to = (dp[i][j][t] + arr[i+1][j+1]) % k;
- if(dp[i+1][j+1][to] < dp[i][j][t] + arr[i+1][j+1])
- dp[i+1][j+1][to] = dp[i][j][t] + arr[i+1][j+1],
- from[i + 1][j + 1][(dp[i][j][t] + arr[i+1][j+1])%k] = -1;
- if(dp[i+1][j+1][to] < dp[i][j][t] + arr[i+1][j+1])
- dp[i+1][j+1][to] = dp[i][j][t] + arr[i+1][j+1],
- from[i + 1][j + 1][(dp[i][j][t] + arr[i+1][j+1])%k] = -1;
- 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]);
- }
- }
- }
- int ma=-1,indma=0;
- for (int i=1;i<=m;i++)
- {
- if (ma<dp[n][i][0])
- {
- ma=dp[n][i][0];
- indma=i;
- }
- }
- if (indma==0||ma==0)
- cout<<-1;
- else
- {
- cout<<ma<<endl;
- int i=n;
- int kcur=0;
- while (i-1)
- {
- if (indma==1)
- indma=2, s.push_back('L'), kcur = (kcur + k - arr[i][indma] % k) % k;
- else if (indma==m)
- indma=m-1, s.push_back('R'), kcur = (kcur + k - arr[i][indma] % k) % k;
- else
- {
- // cerr << "sdf : " << i << endl;
- int newk = (kcur + k - arr[i][indma] % k) % k;
- if (dp[i-1][indma-1][newk] == dp[i][indma][kcur]-arr[i][indma])
- indma--, s.push_back('R');
- else indma++, s.push_back('L');
- kcur = newk;
- }
- i--;
- }
- cout<<indma<<endl;
- while (s.size())
- {
- auto c=s.back();
- s.pop_back();
- cout<<c;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement