Cerinta completa

You are playing a matrix-based game with the following setup and rules:

  • You are given a matrix with rows and columns. Each cell contains some points. When a player passes a cell their score increases by the number written in that cell and the number in the cell becomes . (If the cell number is positive their score increases, otherwise it decreases.)
  • The player starts from any cell in the first row and can move left, right or down.
  • The game is over when the player reaches the last row and stops moving.

image

Print the maximum score that the player can get.

Input Format

The first line contains and . The next lines contain numbers each, number in line denotes the number that is written on cell .

Constraints

Subtasks

  • for tests .
  • for tests .

Output Format

Print the maximum score that the player can get.

Sample Input 0

4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20

Sample Output 0

37

Explanation 0

Refer the image given in statement, the path followed is summing upto .
Note that, is traversed times, but the second time it only contributes to the sum.

Limbajul de programare folosit: cpp14

Cod:

#include <stdio.h>
#include <stdlib.h>
int max(int x,int y);
int N,*table[4000000],*dp,*tdp,*left_sum,*right_sum,*dp_left_tree;

int main(){
  int n,m,ma,total,i,j;
  scanf("%d%d",&n,&m);
  dp=(int*)malloc(m*sizeof(int));
  tdp=(int*)malloc(m*sizeof(int));
  left_sum=(int*)malloc(m*sizeof(int));
  right_sum=(int*)malloc(m*sizeof(int));
  dp_left_tree=(int*)malloc(m*sizeof(int));
  for(i=0;i<n;i++)
    table[i]=(int*)malloc(m*sizeof(int));
  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      scanf("%d",&table[i][j]);
  for(i=0;i<n;i++){
    for(j=total=0;j<m;j++){
      if(j)
        left_sum[j]=table[i][j]+left_sum[j-1];
      else
        left_sum[j]=table[i][j];
      total+=table[i][j];
    }
    for(j=m-1;j>=0;j--)
      if(j!=m-1)
        right_sum[j]=table[i][j]+right_sum[j+1];
      else
        right_sum[j]=table[i][j];
    for(j=m-2;j>=0;j--)
      left_sum[j]=max(left_sum[j],left_sum[j+1]);
    for(j=1;j<m;j++)
      right_sum[j]=max(right_sum[j],right_sum[j-1]);
    if(i){
      for(j=0;j<m;j++)
        dp_left_tree[j]=dp[j]+left_sum[j];
      for(j=m-2;j>=0;j--)
        dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j+1]);
      for(j=0;j<m;j++)
        tdp[j]=right_sum[j]+dp_left_tree[j]-total;
      for(j=0;j<m;j++)
        dp_left_tree[j]=dp[j]+right_sum[j];
      for(j=1;j<m;j++)
        dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j-1]);
      for(j=0;j<m;j++){
        if(left_sum[j]+dp_left_tree[j]-total>tdp[j])
          tdp[j]=left_sum[j]+dp_left_tree[j]-total;
      }
      for(j=0;j<m;j++)
        dp[j]=tdp[j];
    }
    else
      for(j=0;j<m;j++)
        dp[j]=left_sum[j]+right_sum[j]-total;
  }
  for(i=0,ma=-1000000001;i<m;i++)
    if(dp[i]>ma)
      ma=dp[i];
  printf("%d",ma);
  return 0;
}
int max(int x,int y){
  return (x>y)?x:y;
}

Scor obtinut: 1.0

Submission ID: 464647586

Link challenge: https://www.hackerrank.com/challenges/matrix-land/problem

Matrix Land