My logic for CHECHOC:
Notice that we can divide each matrix into sub-matrices of size 2 x 1.
And each sub-matrix can have a maximum sum = min(2*x, y).
In case of odd m and n, a 1 x 1 matrix is left whose maximum sum can be min(x, y) .
This approach gives a WA. Can someone please provide a countercase? @aneee004@therealnishuz
#include <bits/stdc++.h>
#define vi vector<int>
#define pi pair<int, int>
#define vs vector<string>
#define ll long long int
#define pb push_back
#define mod 1000000007
#define INF 1e9
#define f first
#define s second
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n, m, x, y;
cin >> n >> m >> x >> y;
ll ans = 0;
if(m%2 == 0 || n%2 == 0) cout << ((m*n)/2)*min(2*x, y);
else{
cout << ((n*m)/2)*min(2*x, y) + min(x, y);
}
}
return 0;
}
Consider test case : 1 1 11 7
For this case, there are no adjacent cells in the 1x1 matrix. So, the cell can hold the value of x even if it exceeds ‘y’. This is the only corner case due to which many must have got WA.
you are give a constraint for individual cells and a constraint for pairs of cells. When you only have one cell, there are no pairs, so the second condition doesn’t apply to anything.
I don’t really think this 1x1 was an edge case tbh. It was more of an ambiguous problem statement. Like I had already thought of this case but kept it because even though there are no adjacent cells, still it does count as a cell in the sum of two adjacent cells. The problem setters could have even done the opposite for this 1x1 matrix and would call it an edge case lol.
