LeetCode Weekly Contest 207 3問目 - Maximum Non Negative Product in a Matrix [1594]

Source

LeetCode Weekly Contest 207
問題文

問題概要

省略

解法

省略

cLay（version 20200920-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

ll mx[15][15], mn[15][15];

class Solution {
public:
  int maxProductPath(vector<vector<int>>& A) {
    int x = A.size(), y = A[0].size();
    mx[0][0] = mn[0][0] = A[0][0];
    rep(i,1,x) mx[i][0] = mn[i][0] = mn[i-1][0] * A[i][0];
    rep(j,1,y) mx[0][j] = mn[0][j] = mn[0][j-1] * A[0][j];
    rep(i,1,x) rep(j,1,y){
      mx[i][j] = max(mx[i-1][j]*A[i][j], mn[i-1][j]*A[i][j], mx[i][j-1]*A[i][j], mn[i][j-1]*A[i][j]);
      mn[i][j] = min(mx[i-1][j]*A[i][j], mn[i-1][j]*A[i][j], mx[i][j-1]*A[i][j], mn[i][j-1]*A[i][j]);
    }
    if(mx[x-1][y-1] < 0) return -1;
    return mx[x-1][y-1] % MD;
  }
};

Current time: 2024年04月26日22時02分15秒
Last modified: 2020年09月20日14時41分20秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)

ログイン：