fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long 
  4. int t;
  5. signed main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9. 	cin >> t;
  10.     while(t--){
  11.         int n, m;
  12.         cin >> n >> m;
  13.  
  14.         vector<vector<int>> a(n+1, vector<int>(m+1));
  15.         for(int i=1;i<=n;i++)
  16.             for(int j=1;j<=m;j++)
  17.                 cin >> a[i][j];
  18.  
  19.         vector<vector<int>> row(n+1, vector<int>(m+1,0));
  20.         int S = 0;
  21.         for(int i=1;i<=n;i++){
  22.             for(int j=1;j<=m;j++)
  23.                 row[i][j] = row[i][j-1] + a[i][j];
  24.             S += row[i][m];
  25.         }
  26.  
  27.         vector<vector<char>> dp(n+1, vector<char>(S+1, 0));
  28.         vector<vector<int>> par_sum(n+1, vector<int>(S+1, -1));
  29.         vector<vector<int>> par_col(n+1, vector<int>(S+1, -1));
  30.  
  31.         dp[0][0] = 1;
  32.  
  33.         for(int i=1;i<=n;i++){
  34.             for(int prev=0;prev<=S;prev++){
  35.                 if(!dp[i-1][prev]) continue;
  36.                 for(int j=1;j<=m;j++){
  37.                     int cur = prev + row[i][j];
  38.                     if(cur > S) continue;
  39.                     if(!dp[i][cur]){
  40.                         dp[i][cur] = 1;
  41.                         par_sum[i][cur] = prev;
  42.                         par_col[i][cur] = j;
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.  
  48.         int best = 0;
  49.         for(int x=0;x<=S;x++){
  50.             if(dp[n][x]){
  51.                 if(abs(2*x - S) < abs(2*best - S))
  52.                     best = x;
  53.             }
  54.         }
  55.  
  56.         cout << best * (S - best) << "\n";
  57.  
  58.         vector<int> c(n+1);
  59.         int cur = best;
  60.         for(int i=n;i>=1;i--){
  61.             c[i] = par_col[i][cur];
  62.             cur = par_sum[i][cur];
  63.         }
  64.  
  65.  
  66.         string path;
  67.         int col = 1;
  68.         for(int i=1;i<=n;i++){
  69.             while(col < c[i]){
  70.                 path.push_back('R');
  71.                 col++;
  72.             }
  73.             if(i < n) path.push_back('D');
  74.         }
  75.         while((int)path.size() < n + m - 2)
  76.             path.push_back('R');
  77.  
  78.         cout << path << "\n";
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
5 5
1 0 1 1 0
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
5 4
0 0 1 0
0 1 1 1
1 0 0 1
0 1 0 1
0 0 1 0
3 2
1 0
0 1
1 1
stdout
copy 
30
DDDRRRDR
20
DDDRRRD
4
DDR
https://ideone.com/qQZM0a
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!