貌似不用做前缀和也能过?
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int d,N;
ll sum[maxn][maxn]; int main(){
int i,j,k;
d=rd(),N=rd();
for(i=;i<=N;i++){
int a=rd(),b=rd(),c=rd();
sum[a][b]=c;
}
for(i=;i<=;i++){
for(j=;j<=;j++){
sum[i][j]+=(i?sum[i-][j]:)+(j?sum[i][j-]:)-(i&&j?sum[i-][j-]:);
}
}
ll mm=;int cnt=;
for(i=;i<=;i++){
for(j=;j<=;j++){
int i0=max(,i-d),j0=max(,j-d),ii=min(,i+d),jj=min(,j+d);
ll x=sum[ii][jj]-(j0?sum[ii][j0-]:)-(i0?sum[i0-][jj]:)+(i0&&j0?sum[i0-][j0-]:);
if(x>mm) mm=x,cnt=;
else if(x==mm) cnt++;
}
}
printf("%d %lld\n",cnt,mm);
return ;
}
luogu2038 [NOIp2014]无线网络发射器选址 (前缀和)的更多相关文章
-
NOIP2014 无线网络发射器选址
1.无线网络发射器选址 (wireless.cpp/c/pas) [问题描述] 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平 ...
-
关于NOIP2014“无线网络发射器选址”一题的衍生题目的思考及思维方向
无线网络发射器选址 题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形 ...
-
NOIP2014无线网络发射器选址改编1
问题描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平 ...
-
noip2014无线网络发射器选址
题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的 129 条东西向街道和 129 条南北向街道所形成的网格状,并且 ...
-
[NOIP2014] 提高组 洛谷P2038 无线网络发射器选址
题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状,并且相邻 ...
-
NOIP2014_day2:无线网络发射器选址
#include<stdio.h>//NOIP2014 day2 :无线网络发射器选址 ,max=; ][]; void wifi(int a,int b,int c) { int i,j ...
-
Codevs 3578 无线网络发射器选址== NOIP 2014 Day2 T1
3578 无线网络发射器选址 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 随着智能手机的日益普及,人们对无线网的需求日益增大. ...
-
luogu2038[NOIP2014 T4]无线网络发射器选址
题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状,并且相邻 ...
-
Noip2014 提高组 Day1 T1 生活大爆炸版石头剪刀布 + Day2 T1 无线网络发射器选址
Day1 T1 题目描述 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头.如果两个人出拳一样,则不分胜负.在<生活大爆炸>第二季第8 集中出现了一种石头剪刀布的升级版游戏. 升 ...
随机推荐
-
自动打补丁Bat指令
自动打补丁 补丁放于hotfix文件夹下 for %%i in (hotfix\*.exe) do start /wait %%i /z /u
-
c++中string类型可以直接进行比较
以下代码在Ubuntu14.10下实现 /*------------------------- filename is demo.cpp --------------------------*/ #i ...
-
linux yum安装mongodb
1.yum -y install mongodb-server mongodb 2.service mongod start #启动mongodb 服务 3. ...
-
git 解决每次更新代码都要输入用户名密码的解决方案
使用git pull或者git push每次都需要输入用户名和密码很繁琐,耽误时间,现在教大家一条命令实现保存用户名和密码不用再输入 git config --global credential.he ...
-
docker与虚拟机有何不同
docker与虚拟机有何不同 Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化. 容器技术有 ...
-
UVA1646-Edge Case(递推+斐波那契数列)
Problem UVA1646-Edge Case Time Limit: 3000 mSec Problem Description Input For each test case, you ge ...
-
Lodop导出图片和打印机无关,测试是否有关
Lodop导出的图片,既可以在预览界面另存为,也可以用语句导出.语句导出,可查看本博客的相关博文:Lodop导出图片,导出单页内容的图片 预览的时候,由于选择的打印机不同,而真实的打印机可能有不同的可 ...
-
DateTables的服务器分页
function InitTable() { var table = $('#tbl_users').DataTable(); if ($.fn.dataTable.isDataTable('#tbl ...
-
《剑指offer(第二版)》面试题55——判断是否为平衡二叉树
一.题目大意 输入一颗二叉树,判断该二叉树是否为平衡二叉树(AVL树). 二.题解 <剑指offer>上给出了两种解决方式: 1.第一种是从根节点开始,从上往下遍历每个子节点并计算以子节点 ...
-
python学习之老男孩python全栈第九期_day003知识点总结
1. int: i.bit_length(): 把i这个数转换成二进制所需最少的位数 2. bool: (1) 1比True的效率更高 (2) 空字符串(什么都没有)为False:非空字符串为True ...