I have gone through many posts to identify my mistake but still I am getting it one. Mostly everyone has missed the base case of (1*1) matrix but I have considered that case too, still I am getting WA.
My logic to this question:
First I have checked that base condition where if p = m*n equals 1, answer will be x.
After that I have wrote code for two cases, one for odd p and other for even p.
For the first case when p is even, I first checked u = min(2 * x, y), because any (2x1) sub-matrix will be filled with min(2*x, y) candies.
If u is even, answer will be (p * u/2), where we can fill every (1x1) matrix with can/2 number of candies.
If u is odd, answer would be fill half of (1x1) squares with values (u/2) and half with (u+1)/2.
Let’s consider an example,
3 4 3 5
Here the representation would be,
3 2 3 2
2 3 2 3
3 2 3 2
Here u = min(2 * x,y) which is 5, since 5 is odd we will fill half number of cells with val (can/2) and half with (can+1)/2.
Now come to the case where p is odd, here also I did the same thing, first I found u=min(2 * x, y) and checked whether can is odd or even.
If u is even, answer would be again p*u/2, where we can fill every (1x1) matrix with u/2 number of candies.
If u is odd, we can fill p/2 cells with (u/2 candies) and (p/2)+1 cells with (u+1)/2 number of candies.
Let’s take an example to clear it,
5 5 2 3
Here the representation would be,
2 1 2 1 2
1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
Again u = min(2 * x, y) will be 3 and since 5x5 is odd we will fill (5 * 5/2) + 1 cells with (u+1/2) candies, so basically we will fill 13 cells with 2 candies and rest with 1.
Hope you all understood my logic but still I am getting WA. Any corner case please, I am trying to figure out the reason.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n, m, x, y, res;
cin>>n>>m>>x>>y;
ll p = n*m;
if(p == 1) res = x;
else if(p % 2 == 0)
{
ll can = min(2*x, y);
if(can % 2 == 0) res = p * (can/2);
else
{
ll i = can/2;
ll j = (can+1)/2;
res = (i * p/2) + (j * p/2);
}
}
else if(p % 2 == 1)
{
ll can = min(2*x, y);
if(can % 2 == 0) res = p * (can/2);
else
{
ll i = can/2;
ll j = (can+1)/2;
ll p1 = p/2;
ll p2 = (p+1)/2;
res = (i * p1) + (j * p2);
}
}
cout<<res<<"\n";
}
return 0;
}
Link to my solution : CodeChef: Practical coding for everyone