问题 E: 小李打怪兽II
时间限制: 1 Sec 内存限制: 128 MB
提交 状态
题目描述
在一个弱智游戏里，有m行n列的怪兽，每个怪兽用一个数值表示它的生命值。小李每次的攻击力都为k。
对于小李的每次攻击，给出三个整数x,y,r，表示对于以点(x?r,y?r)为左上角，点(x+r,y+r)为右下角的矩形范围内的怪兽生命值都减去k。怪兽生命值为0时就死了。请计算经过小李g轮的疯狂攻击，还剩几个怪兽存活。
输入
第一行四个整数，分别表示m,n,k,g。
接下来g行整数，每行三个分别表示对应的x,y,r。
接下来是m行n列的正整数ai,j。
输出
一个整数，表示答案。
样例输入 Copy
6 5 2 1
4 3 2
3 2 1 2 5
1 2 4 1 1
3 3 3 1 2
4 43 1 1 5
5 2 2 2 4
1 1 3 1 5
样例输出 Copy
16
提示
对于100%的数据，1≤n,m,x,y,r≤1025,1≤k,a≤100,1≤g≤106
999ms卡出来的题
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1050][1050];
ll qz[1050][1050];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);ll m,n,kk,g;scanf("%lld%lld%lld%lld",&m,&n,&kk,&g);ll x,y,r;for(int i=0;i<g;i++){scanf("%lld%lld%lld",&x,&y,&r);for(int j=y-r;j<=y+r;j++){qz[x-r][j]+=kk;qz[x+r+1][j]-=kk;}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){qz[i][j]=qz[i][j]+qz[i-1][j];}}ll ans=0;for(ll i=1;i<=m;i++){for(ll j=1;j<=n;j++){scanf("%lld",&a[i][j]);if(a[i][j]>qz[i][j]){ans++;}}}cout<<ans<<endl;return 0;
}/**************************************************************Problem: 11795User: 2019UPC110Language: C++Result: 正确Time:999 msMemory:19404 kb
****************************************************************/#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll ans;
ll G[1100][1100],sum[1100][1100];
int main()
{int n,m,k,g;scanf("%d%d%d%d",&n,&m,&k,&g);for(int i=1;i<=g;i++){int x,y,r;scanf("%d%d%d",&x,&y,&r);int x1=max(1,x-r);int y1=max(1,y-r);int x2=min(n,x+r);int y2=min(m,y+r);sum[x1][y1]+=k;sum[x2+1][y1]-=k;sum[x1][y2+1]-=k;sum[x2+1][y2+1]+=k;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&G[i][j]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//cout<<sum[i][j]<<' ';if(sum[i][j]<G[i][j])ans++;}//cout<<endl;}cout<<ans;}