CP02 Editorial

editorial
1

Problem link

Click here

Difficulty

Easy

Solution

Using the given operations you can propagate negative signs to anywhere in the matrix, so we would always bring two negative elements adjacent to each other(diagonally adjacent too) and then by performing one extra operation we can make both of them positive. So in those cases when we have a total even number of negative integers, we can make all of them positive and if we have total odd number of negative integers, then we will, in the end have exactly 1 negative integer, so it is more optimal to keep the element with the smallest absolute value as negative. Note that if we have a 0 in the matrix, then it is always possible to make all the numbers non-negative.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    cin>>n>>m;
    ll mn=1e9;
    ll sum=0;
    int cnt=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            ll num;
            cin>>num;
            sum+=abs(num);
            mn=min(mn,abs(num));
            if(num<0)
             cnt++;
        }
    }
    if(cnt%2)
     cout<<sum-2*mn;
    else
     cout<<sum;
    return 0;
}