fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<limits.h>
  5.  
  6. long long int **a;
  7. long long int **b;
  8. long long int **ans;
  9. long long int *min;
  10.  
  11. long long int min2(long long int a,long long int b)
  12. {
  13.     return a<b?a:b;
  14. }
  15. long long int aa(long long int i,long long int j)
  16. {
  17.     if(a[i][j]-b[i-1][j]<0)
  18.     return ans[i-1][j]-a[i][j];
  19.     else
  20.     return ans[i-1][j]-(b[i-1][j]);
  21. }
  22. long long int bb(long long int i,long long int j)
  23. {
  24.     return min[i-1];
  25. }
  26. main()
  27. {
  28.  
  29.     long long int min1=ULONG_MAX,sum=0,sum1=0;
  30.     long long int i,j,k,x,n,r,m,w,y,z;
  31.    scanf("%lld",&y);
  32.     for(r=y;r>0;r--)
  33.     {
  34.   scanf("%lld %lld",&m,&n);
  35. min1=ULONG_MAX;
  36. //printf("check1\n");
  37. a=(long long int **) malloc(m*sizeof(long long int *));
  38.  
  39. for(i=0;i<m;i++)
  40.     a[i]=(long long int *) malloc(n*sizeof(long long int ));
  41. for( i=0;i<m;i++)
  42. {
  43.     for( j=0;j<n;j++)
  44.    scanf("%lld",&a[i][j]);
  45. }
  46. //printf("check2\n");
  47. b=(long long int **) malloc(m*sizeof(long long int *));
  48.  
  49. for(i=0;i<m;i++)
  50.     b[i]=( long long int *) malloc(n*sizeof(long long int));
  51. for( i=0;i<m;i++)
  52. {
  53.     for( j=0;j<n;j++)
  54.    scanf("%lld",&b[i][j]);
  55. }
  56. //printf("check3\n");
  57. ans=(long long int **) malloc(m*sizeof(long long int *));
  58.  
  59. for(i=0;i<m;i++)
  60.     ans[i]=(long long int *) malloc(n*sizeof(long long int ));
  61. min=(long long int *)malloc(m*sizeof(long long int));
  62.  
  63. for(i=0;i<m;i++)
  64. min[i]=ULONG_MAX;
  65. for(j = 0; j < m; j++)
  66. {  
  67.     for(i=0; i < n; i++)
  68.     {
  69.         ans[j][i]=0;
  70.     }
  71. }
  72. //printf("check5\n");
  73. for(i=0;i<n;i++)
  74.     {ans[0][i]=a[0][i];
  75.     if(min[0]>ans[0][i])
  76.     min[0]=ans[0][i];}
  77.  
  78. for(i=1;i<m;i++)
  79. {
  80.     for(j=0;j<n;j++)
  81.     {
  82.  
  83.         ans[i][j]=min2(aa(i,j),bb(i,j))+a[i][j];
  84.         if(min[i]>ans[i][j])
  85.         min[i]=ans[i][j];
  86.     }
  87.     //printf("\n");
  88.     }
  89.   //  printf("check6\n");
  90. for(i=0;i<n;i++)
  91. {
  92.     if(min1>ans[m-1][i])
  93.     min1=ans[m-1][i];
  94. }
  95. /*
  96. for( i=0;i<m;i++)
  97. {
  98.     for( j=0;j<n;j++)
  99.    printf("%d    ",ans[i][j]);
  100.    printf("\n");
  101. }*/
  102. //printf("out\n");
  103. printf("%lld\n",min1);
  104. for(i=0;i<m;i++)
  105. {
  106.     free(a[i]);
  107.     free(b[i]);
  108.     free(ans[i]);
  109. }
  110. free(a);free(b);free(ans);free(min);
  111. }
  112.  
  113. return 0;
  114.  
  115. }
  116.  
  117.  
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6iCRuT
language:
C++ (gcc 8.3)
created:
10 years 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!