codeJan与恐怖分子

NC14843. codeJan与恐怖分子

描述

把Noland抽象成一个n∗m的方格矩阵，行从上到下为1∼n，列从左到右为1∼m。codeJan处在坐标为(R,C)方格上，codeJan可以观察到他所在的行和列的治安情况。有一个恐怖分子想要毁掉Noland，又不被codeJan观察到。恐怖分子手中有无穷多个可以每次炸毁边长为K∗K的区域。方格矩阵的每个方格的边长为1。炸毁的区域不能超过Noland(方格矩阵)的范围，同一块区域可以炸毁多次。恐怖分子至少需要多少颗炸弹才能炸毁除了codeJan所在的行列的其余所有区域？或者无法完成这个任务？

输入描述

第一行是一个 T(T ≤ 1000) 代表测试组数。接下来 T 行，每行包含 5 个正整数 n, m,R, C,K，含义如上。

输出描述

一共输出 T 行，每行输出一个数字。如果可以完成任务，输出需要的最少的炸弹数量；否则无法完成任务，输出 -1。

示例1

输入:

输出:

0
1
4

说明:

第一个样例，因为只有一个格子且被警察占领，所以不需要额外炸掉格子，所以答案是 0。
第二个样例，只需要炸掉 (2,2) 这个格子，所以需要 1 颗可以炸毁 1*1 的炸弹。
第三个样例，有四个格子需要炸毁，所以需要 4 颗 1*1 的炸弹。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-07-25 16:05:47

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,m,r,c,k;
ll ask(int n,int m){
    if(!n||!m)return 0;
    if(n<k||m<k)return -1LL<<60;
    return (ll)(n+k-1)/k*((m+k-1)/k);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&n,&m,&r,&c,&k);
        cout<<max(ask(r-1,c-1)+ask(n-r,c-1)+ask(r-1,m-c)+ask(n-r,m-c),-1LL)<<endl;
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-11-09 01:29:33

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,m,r,c,k;
ll ask(int n,int m)
{
	if(!n||!m)return 0;
	if(n<k||m<k)return -1LL<<60;
	return (ll)(n+k-1)/k*((m+k-1)/k);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d%d",&n,&m,&r,&c,&k);
		cout<<max(ask(r-1,c-1)+ask(n-r,c-1)+ask(r-1,m-c)+ask(n-r,m-c),-1LL)<<endl;
	}
	return 0;
}